Sexuality and sex education cannot be divorced from the moral values of the societies within which we must negotiate our sexual identities and relationships. Rather than pandering to the moral panic that is too often associated with the provision of sex education in non-secular societies where religion is more visibly active in shaping sexual ideals and norms, this article takes up the challenge of investigating a relationship that is often represented as being innately contradictory. It explores the Islamic notion of "zina" (illicit sex) in relation to the provision of comprehensive sex education for Muslim youth in contemporary Indonesia. The article initially establishes the demand for sex education among Indonesian youth from the overlapping perspectives of health, human rights and Islam. It then explores the notion of "zina" in detail and exposes how Islamic stipulations against premarital sex are not necessarily in conflict with the provision of sex education. The final section of the article refines the argument in favour of utilizing Islam as a framework for developing religiously appropriate sex education and describes a suitable approach and content for Islamic sex education curricula for Indonesian youth. (Contains 8 notes.)