The use of biological control agents (BCA), alone or in combination with other management measures, has gained attention over the past decades, driven by the need to seek for sustainable and eco-friendly alternatives to confront plant pathogens. The rhizosphere of olive (Olea europaeaL.) plants is a source of bacteria with potential as biocontrol tools against Verticillium wilt of olive (VWO) caused byVerticillium dahliaeKleb. A collection of bacterial isolates from healthy nursery-produced olive (cultivar Picual, susceptible to VWO) plants was generated based on morphological, biochemical and metabolic characteristics, chemical sensitivities, and on theirin vitroantagonistic activity against several olive pathogens. Three strains (PIC25, PIC105, and PICF141) showing highin vitroinhibition ability of pathogens' growth, particularly againstV. dahliae, were eventually selected. Their effectiveness against VWO caused by the defoliating pathotype ofV. dahliaewas also demonstrated, strain PICF141 being the rhizobacteria showing the best performance as BCA. Genotypic and phenotypic traits traditionally associated with plant growth promotion and/or biocontrol abilities were evaluated as well (e.g., phytase, xylanase, catalase, cellulase, chitinase, glucanase activities, and siderophore and HCN production). Multi-locus sequence analyses of conserved genes enabled the identification of these strains asPseudomonasspp. Strain PICF141 was affiliated to the "Pseudomonas mandeliisubgroup," within the "Pseudomonas fluorescensgroup,"Pseudomonas linibeing the closest species. Strains PIC25 and PIC105 were affiliated to the "Pseudomonas aeruginosagroup,"Pseudomonas indicabeing the closest relative. Moreover, we identifiedP. indica(PIC105) for the first time as a BCA. Genome sequencing andin silicoanalyses allowed the identification of traits commonly associated with plant-bacteria interactions. Finally, the root colonization ability of these olive rhizobacteria was assessed, providing valuable information for the future development of formulations based on these strains. A set of actions, from rhizosphere isolation to genome analysis, is proposed and discussed for selecting indigenous rhizobacteria as effective BCAs.