Microbes establish very diverse but still poorly understood associations with other microscopic or macroscopic organisms that do not follow the more conventional modes of competition or mutualism. Phaffia rhodozyma, an orange-coloured yeast that produces the biotechnologically relevant carotenoid astaxanthin, exhibits a Holarctic association with birch trees in temperate forests that contrasts with the more recent finding of a South American population associated with Nothofagus (southern beech) and with stromata of its biotrophic fungal parasite Cyttaria spp. We investigated whether the association of Phaffia with Nothofagus-Cyttaria could be expanded to Australasia, the other region of the world where Nothofagus are endemic, studied the genetic structure of populations representing the known worldwide distribution of Phaffia and analysed the evolution of the association with tree hosts. The phylogenetic analysis revealed that Phaffia diversity in Australasia is much higher than in other regions of the globe and that two endemic and markedly divergent lineages seem to represent new species. The observed genetic diversity correlates with host tree genera rather than with geography, which suggests that adaptation to the different niches is driving population structure in this yeast. The high genetic diversity and endemism in Australasia indicate that the genus evolved in this region and that the association with Nothofagus is the ancestral tree association. Estimates of the divergence times of Phaffia lineages point to splits that are much more recent than the break-up of Gondwana, supporting that long-distance dispersal rather than vicariance is responsible for observed distribution of P. rhodozyma.