Since the majority of Indonesia’s population is Muslim, their adoption of Islamic norms in the context of sexuality education is important. However, in reality there are gaps between Islamic doctrines and adolescents’ sexual views and behavior. Sexual relationships outside marriage are negotiated among young people in Islamic communities. This paper describes tensions and paradoxes in Muslim adolescents’ views and practices on sexuality and their implications for the approaches used in sexuality education in Islamic boarding schools in Indonesia. The study found that although the dominant discourse of Islamic norms and Indonesian youth policies and programs highlights the dangers of premarital sex in order to prevent young people from being promiscuous, young people have ambivalent views and practices on premarital sex. The sexuality education constitutes an arena of intersections of Islamic norms, Indonesian state and global discourses on adolescents’ sexual and reproductive rights, and adolescents’ narratives. In reframing comprehensive sexuality education for the youth, the views of adolescents should be at its core.