Ab initio downfolding describes the electronic structure of materials within a low-energy subspace, often around the Fermi level. Typically starting from mean-field calculations, this framework allows for the calculation of one- and two-electron interactions, and the parametrization of a many-body Hamiltonian representing the active space of interest. The subsequent solution of such Hamiltonians can provide insights into the physics of strongly correlated materials. While phonons can substantially screen electron-electron interactions, electron-phonon coupling has been commonly ignored within ab initio downfolding, and when considered, this is done only for short-range coupling. Here we propose a theory of ab initio downfolding that accounts for short- and long-range electron-phonon coupling on equal footing. Our practical computational implementation is readily compatible with current downfolding approaches. We apply our approach to polar materials MgO and GeTe, and we reveal...