Olea europaea (L.) trees displaying leaf scorching symptoms, identical to those recently reported for olive trees colonized by Xylella fastidiosa in Southern Italy and also in Argentina, were observed in commercial orchards of two counties in Southeastern Brazil. PCR-based diagnosis using conserved primers for X. fastidiosa strains (RST31/33) and also specific to X. fastidiaosa subsp. pauca (CVC1/272-2 int) were positive for all symptomatic tested samples (n = 8 of 9), but no template was obtained using twigs from asymptomatic trees (n = 20). Bacterial colonies were isolated from symptomatic tissues on culture medium and confirmed by PCR using the set of primers specific to X. fastidiosa subsp. pauca. Comparative sequence analyses of seven MLST loci amplified from one tripled passaged colony (MFG01) perfectly matched with sequences of alleles leuA #7, petC #6, malF#8, cysG#10, holC# 11, nuoL#8, and gltT#8, the allelic profile of Sequence Type-ST16, which is represented by the strain COF0238 isolated from Coffea arabica (L.) in Brazil (http://pubmlst.org/xfastidiosa/). Phylogenetic analysis placed the ST16 into subspecies pauca, but genetically closer to ST11 and ST13, both obtained from Citrus sinensis (L.) trees with citrus variegated chlorosis. The results confirm the association of olive plants showing leaf scorching with the presence of X. fastidiosa subsp. pauca, and represent the first report of this bacterium in Brazilian olive orchards.