This article addresses how sex education in Zambia has changed over the course of time, particularly due to the spread of HIV/AIDS. The article is based on fieldwork conducted by the author in Zambia during six periodsbetween 1992 and 2003, and additional literature on HIV/AIDS education. The research conducted by the author between 1992 and 2001 focused primarily on female initiation rites, while that of 2002-2003 focused on the knowledge of HIV/AIDS among Zambian youth and how the knowledge is passed on by teachers at primary schools, but also by health workers, peer educators, and parents. For this study personal and group interviews were held with children, teachers, health workers, peer educators, and parents. This article focuses on sex education in the past, such as given during intitiation rites, and today as given in schools, and examine how sex education for girls and boys both in traditional and modern teaching has been changing. It analyses sexual relationships between young people and notions of sexuality in Zambia. It also pays attention to gender aspects among boys and girls and in relation to HIV/AIDS in Zambia.