Internationally, school-based sexuality education programmes have shown to improve sexual practices and health outcomes for young people. However, perceived parental discord is commonly cited as a barrier to implementation. Within Indonesia, there is limited empirical evidence regarding parents' attitudes towards school-based sexuality education. A sample of 768 Indonesian parents and caregivers completed an online Qualtrics survey to determine their level of support or disapproval towards the provision of sexuality education within primary and secondary schools. The majority of parents supported school-based sexuality education (n = 756, 98.4%) and suggested certain topics should commence as early as kindergarten and elementary school (n = 615, 80.0%). Religious affiliation was not associated with permissiveness. When presented with a range of sexuality topics, most parents agreed their inclusion was important. However, for some topics, there was significant variability in opinion based upon the age, gender, or educational background of the parent; thereby providing opportunity for further work. This preliminary study challenges notions that parents, particularly those with religious affiliations, are barriers to the delivery of sexuality education within Indonesia schools. Further research and advocacy will hopefully encourage educators to expand their current levels of provision, to align with international and evidence-based guidelines.