Excitons consist of electrons and holes held together by their attractive Coulomb interaction. Although excitons are neutral excitations, spatial fluctuations in their charge density couple with the ions of the crystal lattice. This coupling can lower the exciton energy and lead to the formation of a localized excitonic polaron or even a self-trapped exciton in the presence of strong exciton-phonon interactions. Here, we develop a theoretical and computational approach to compute excitonic polarons and self-trapped excitons from first principles. Our methodology combines the many-body Bethe-Salpeter approach with density-functional perturbation theory and does not require explicit supercell calculations. As a proof of concept, we demonstrate our method for a compound of the halide perovskite family.