Olive quick decline syndrome (OQDS), which is caused by Xylella fastidiosa, poses a severe threat to the agriculture of Mediterranean countries and causes severe damage to the olive trees in Italy. Since no effective control measures are currently available, the objective of this study was the screening of antagonistic bacteria that are potentially deployable as biocontrol agents against X. fastidiosa. Therefore, two approaches were used, i.e., the evaluation of the antagonistic activity of (i) endophytic bacteria isolated from two different cultivars of olive trees (Leccino and Ogliarola salentina) and (ii) epiphytic bacteria isolated from the phyllospheres of different host plant species of X. fastidiosa. In vitro dual culture tests showed that 12 out of 200 isolates inhibited X. fastidiosa growth, with appearances of clear zones between 4.0 and 38.6 mm. 16S rRNA gene sequencing revealed different species of the genera Paenibacillus, Bacillus, Pantoea, Microbacterium, Stenotrophomonas, Delftia, and Pseudomonas. Furthermore, an investigation for antimicrobial activity identified 5 out of the 12 antagonistic bacteria, Paenibacillus rigui, Bacillus subtilis, Bacillus pumilus, Microbacterium oxydans, and Stenotrophomonas rhizophila, that were able to produce culture filtrates with inhibitory activities. Our results are promising for further investigation to develop an eco-sustainable strategy to control X. fastidiosa using biocontrol agents or their secreted metabolites.