The rust fungus, Puccinia psidii, is a devastating pathogen of introduced eucalypts (Eucalyptus spp.) in Brazil where it was first observed in 1912. This pathogen is hypothesized to be endemic to South and Central America and to have first infected eucalypts via a host jump from native guava (Psidium guajava). Ten microsatellite markers were used to genotype 148 P. psidii samples from eucalypts and guava plus five additional myrtaceous hosts across a wide geographic range of southeastern Brazil and Uruguay. Principal coordinates analysis, a Bayesian clustering analysis, and a minimum spanning network revealed two major genetic clusters among the sampled isolates, one associated with guava and another associated with eucalypts and three additional hosts. Multilocus genotypes infecting guava differed by multiple mutational steps at eight loci compared to those infecting eucalypts. Approximate Bayesian computation revealed that evolutionary scenarios involving a coalescence event between guava- and eucalypt-associated pathogen populations within the past 1000 years to be highly unlikely. Divergence time estimates conducted over a wide range of demographic scenarios indicated that the population split between eucalypt- and guava-infecting pathogens occurred approximately 15,000 to 150,000 years ago. None of the analyses supported the hypothesis that eucalypt-infecting P. psidii in Brazil originated via host jump from guava since the introduction of eucalypts to Brazil approximately 185 years ago. The existence of host-associated biotypes of P. psidii in Brazil indicates that this diversity must be considered when assessing the invasive threat posed by this pathogen to myrtaceous hosts worldwide.