Background: Sexually transmissible infections (STIs) among young Australians increased dramatically between 1997 and 2007 with rates of chlamydia increasing by 528% and rates of gonorrhoea by 169% among 15–19 year olds. High notification rates of STIs and teenage pregnancy point to the need to investigate sexual health education (SHE) in Australian schools. This first quantitative study investigated the attitudes and experiences of parents to SHE in Australian schools. Methods: One hundred and seventeen (117) Australian parents were recruited through purposive sampling and snowballing methods to complete an online questionnaire in 2007. Results: Most respondents (97.4%) support SHE in schools and 95.7% advocate schools and parents sharing responsibility. A majority (82.9%) believe SHE should begin in primary school with discrepancy as to when specific topics should be introduced. There is consensus for a comprehensive curriculum, including topics potentially seen as controversial such as ‘masturbation’. ‘Abstinence’ was chosen by 15.4% of parents to not be included in SHE curricula. Most parents rate the SHE their children have received in school as ‘fair’ in quality, and want access to resources to help them educate their children, including workshops at schools, information about school SHE, literature, and trained sexual health educators. Conclusions: Parents generally support SHE in schools. They want programs to begin in primary school. They consider the current school programs to be ‘fair’ in quality. Parents also point out the need for a more comprehensive curriculum and they want to be involved with schools in the development and delivery of SHE.