In Brazil, the host expansion of Xylella fastidiosa subsp. pauca was recently demonstrated with the report of diseased olive trees (Olea europaea), whose symptoms were associated with olive quick decline syndrome previously described in southern Italy. We employed both polymerase chain reaction-based techniques and culture medium isolation to investigate the geographic distribution of X. fastidiosa as well as the genetic signatures of 21 strains isolated from 11 olive orchards in both Sao Paulo and Minas Gerais States in Brazil. X. fastidiosa subsp. pauca was detected in 83% of the orchards examined in the region, and was positively diagnosed in 43.7% of all sampled plants with typical scorching symptoms. Of the 21 strains characterized with fast-evolving microsatellite (single sequence repeat [SSR]) markers, 20 different multilocus microsatellite genotypes were observed with the overall allelic diversity of H-Nei = 0.38. Principal component analysis using the SSR markers clustered all strains, except for three, in one cluster demonstrating a limited range of genetic diversity. Multilocus sequence typing analysis showed the prevalence of a sequence type (ST16) in 75% of the samples; three other novel STs (84, 85, and 86), were detected, all belonging to the X. fastidiosa subsp. pauca cluster. These results show that genetically diverse strains of X. fastidiosa subsp. pauca are widely present in olive orchards in southeastern Brazil, which is consistent with the long history of this bacterium in that region.