Background: Vaccination rates have remained steady for a number of years in Australia, however geographical areas of lower vaccine coverage remains a day-to-day challenge. The study explores parental attitudes, beliefs and intentions in relation to vaccination and examines the early effects of recent No Jab No Pay legislation. Methods: A national survey of was conducted, using an online questionnaire. Parents from all states in Australia with at least one child aged <6 years were invited to participate. Results: A total of 429 parents participated in the study. The substantial majority of participants reported having their youngest child's vaccination status up to date (n = 401, 93.5%). A child's vaccinations were more likely to be up to date if they had consulted a paediatrician in the previous 12-months (OR 5.01; 95%CI 1.05, 23.92; p = .043). Conversely they were less likely to be vaccinated if they were influenced by information from a complementary medicine (CM) practitioner (OR 0.03; 95%CI 0.01, 0.15; p < .001) or had visited a CM-practitioner (OR 0.09; 95%CI 0.02, 0.33; p < .001) in the previous 12-months. A total of 2.6% of parents had immunised their child as a result of the No Jab No Pay legislation, while 3.9% stated the legislation had no effect, and 1.2% said it had made them less likely to vaccinate. A further 1.2% of parents stated they are considering vaccination as a result of the legislative changes. Conclusion: Parents who have not vaccinated their children appear to trust non-mainstream sources of information such as CM-practitioners. Further research is required to determine how to manage the challenges and opportunities of CM-practitioners as a source of vaccine information.