We present a theoretical framework to describe polarons from first principles within a many-body Green's function formalism. Starting from a general electron-phonon Hamiltonian, we derive a self-consistent Dyson equation in which the phonon-mediated self-energy is composed by two distinct terms. One term is the Fan-Migdal self-energy and describes dynamic electron-phonon processes, the other term is a contribution to the self-energy originating from the static displacements of the atomic nuclei in the polaronic ground state. The lowest-order approximation to the present theory yields the standard many-body perturbation theory approach to electron-phonon interactions in the limit of large polarons, and the ab initio polaron equations introduced [Sio et al., Phys. Rev. B 99, 235139 (2019)2469-995010.1103/PhysRevB.99.235139; Phys. Rev. Lett. 122, 246403 (2019)0031-900710.1103/PhysRevLett.122.246403] in the limit of small polarons. A practical recipe to implement the present unifying formalism in first-principles calculations is outlined. We apply our method to the Fröhlich model, and obtain remarkably accurate polaron energies at all couplings, in line with Feynman's polaron theory and diagrammatic Monte Carlo calculations. We also recover the well-known results of Fröhlich and Pekar at weak and strong coupling, respectively. The present approach enables predictive many-body calculations of polarons in real materials at all couplings.