Objective: Using a conceptual model of school-based implementation, this study aimed to explore teachers’ implementation of Relationships and Sexuality Education (RSE) in a school context. Design and Method: A model of school-based implementation was derived from a review of the literature and a mixed methods approach was employed to examine components of the model. The components included: program model; quality of delivery; target audience; participant responsiveness; pre-planning; quality of materials; technical support model; quality of technical support; implementer readiness and factors relating to the context (classroom, district, school and community). Data were drawn from lesson plans, questionnaires, self-report forms, nonparticipant observation, and semi-structured interviews. Results: Students rated lesson resources highly (quality of materials) and more than three-quarters of students found RSE classes interesting (participant responsiveness). All teachers valued the importance of RSE (implementer readiness) but overcomplicated lessons prevented teachers from achieving lesson aims (pre-planning). Didactic, as opposed to facilitative approaches, were employed to implement RSE which opposes the core principle of the program (quality of delivery). The study also found that school leadership and management have a major role to play in the implementation of RSE through, for example, the appointment of teachers to the delivery of RSE and controlling access to RSE training (contextual level factors). Conclusions: The implementation of RSE is more contentious than other school-based health education programs. Stringent pre-planning and whole-school support is essential for successful implementation.