The genus Ceratocystis includes important fungal pathogens of trees, including Eucalyptus spp. Ironically, very little is known regarding the diversity or biology of Ceratocystis species on Eucalyptus species in Australia, where most of these trees are native. The aim of this study was to survey for Ceratocystis spp., and their possible insect associates, on eucalypts in Australia and thus to establish a foundation of knowledge regarding these fungi on the continent. Collections were made in three states of Australia from wounds on trees, as well as from nitidulid beetles associated with these wounds. Ceratocystis spp. were identified based on morphology and multigene sequence comparisons. Of the 54 isolates obtained, two previously unknown species of Ceratocystis were found and these are described here as Ceratocystis corymbiicola sp. nov. and Ceratocystis tyalla sp. nov. Furthermore, the distribution of Ceratocystis pirilliformis is expanded to include Eucalyptus spp. in Tasmania.