This case study investigated teachers’ perceptions of contextual influences on their instruction and student engagement on sexuality discourses within four selected schools in Kampala, Uganda. The question that guided the study was: What and how are the contextual factors as perceived by health education teachers in Uganda influencing classroom discourses on sexuality? The research is grounded within two relevant theoretical frameworks; constructivism and the conceptual change theory (CCT). Constructivism acknowledges that individuals have preconceived notions rooted in their social, cultural and historical backgrounds, and CCT enables teachers to develop strategies that allow learners opportunities to reexamine their preconceptions about phenomena with a view of aligning them with canonical science. Through a narrative methodological approach, teachers narrated their stories based on their lived classroom experiences. Data sources included researcher’s field notes, e-mail correspondences, semi-structured questionnaires, and audio recordings of the teachers’ narratives. The data corpus was analyzed following intense dialogic analysis procedures, which encompassed elements of thematic and structural analytical methods as well as other broad interpretive dimensions such as how talk among speakers is dialogically produced. The findings revealed that while there is some form of sexuality education in schools and while teachers are very enthusiastic about its implementation, it is largely constrained by a plethora of contextual factors.