Coral reefs, critically endangered by climate warming, urgently require innovative, scalable interventions. Probiotics offer promise, but stability and effectiveness need improvement. We introduce an evolutionary genomic framework for selecting so-called next-generation probiotics using host adaptation signatures. Targeting bacteria transitioning irreversibly to host dependency, we identify coral-sourced Ruegeria MC10, exhibiting insertion sequence proliferation and essential gene pseudogenization. In a proof-of-principle, coral model cnidarians showed increased thermal tolerance. Subsequent, real-world application of one-month nursery inoculations enabled Acropora pruinosa corals to retain MC10 for the monitored period (eight months) post-outplanting, including persistence through a natural bleaching event, with sustained coloration. MC10 colonized the gastrodermis, exhibited host flexibility, and minimally disrupted native microbiomes. This work pioneers a scalable, evolution-guided strategy for microbial-driven reef restoration, applicable to wildlife at large.