High-yielding microalgae present an important commodity to sustainably satisfy burgeoning food, feed and biofuel demands. Because algae-associated bacteria can significantly enhance or reduce yields, we isolated, identified and selected highly-effective "probiotic" bacterial strains associated with Nannochloropsis oceanica, a high-yielding microalga rich in eicosapentaenoic acid (EPA). Xenic algae growth was significantly enhanced by co-cultivation with ten isolated bacteria that improved culture density and biomass by 2.2- and 1.56-fold, respectively (1.39 × 108 cells mL-1; 0.82 g L-1). EPA contents increased up to 2.25-fold (to 39.68% of total fatty acids). Added probiotic bacteria possessed multiple growth-stimulating characteristics, including atmospheric nitrogen fixation, growth hormone production and phosphorous solubilization. Core N. oceanica-dominant bacterial microbiomes at different cultivation scales included Sphingobacteria, Flavobacteria (Bacteroidetes), and α, γ-Proteobacteria, and added probiotic bacteria could be maintained. We conclude that the supplementation with probiotic algae-associated bacteria can significantly enhance biomass and EPA production of N. oceanica.