Background: Despite recommendations that pre-school children use toothpaste containing 500–550 ppm of fluoride, there has been an increase in non-fluoridated toothpastes marketed for children. This study investigated children’s toothpaste in Australia. Methods: A comprehensive audit of all toothpastes marketed for pre-school children and available in store in the Macarthur region of NSW, Australia, was carried out. All toothpastes available for purchase were obtained and examined; size and price were catalogued, along with ingredient lists and fluoride levels. Results: One hundred and seven individual toothpastes were identified in the audit, with 67 (62.6%) containing no fluoride. Of the 40 fluoridated toothpastes, only 11 (10.3%) contained the recommended level of fluoride of 500–550 ppm. Twenty-two (20.6%) of all toothpastes were made in Australia, all of which were non-fluoridated. Six (5.6%) of the toothpastes studied contained excessive levels of fluoride (1350–1500 ppm). Seventeen of the 20 least expensive toothpastes contained fluoride, while 18 of the 20 most expensive toothpastes were non-fluoridated. Conclusions: Despite expert recommendations, the majority of children’s toothpaste available in Australia contains either no fluoride or the wrong levels of fluoride. Further study is needed to determine why this change is occurring and what is influencing the increase in non-fluoride toothpastes on the market.