Understanding electronic interactions in high-temperature superconductors is an outstanding challenge. In the widely studied cuprate materials, experimental evidence points to strong electron-phonon (e-ph) coupling and broad photoemission spectra. Yet, the microscopic origin of this behavior is not fully understood. Here we study e-ph interactions and polarons in a prototypical parent (undoped) cuprate, La₂CuO₄ (LCO), by means of first-principles calculations. Leveraging parameter-free Hubbard-corrected density functional theory, we obtain a ground state with band gap and Cu magnetic moment in nearly exact agreement with experiments. This enables a quantitative characterization of e-ph interactions. Our calculations reveal two classes of longitudinal optical (LO) phonons with strong e-ph coupling to hole states. These modes consist of Cu-O plane bond-stretching and bond-bending as well as vibrations of apical O atoms. The hole spectral functions, obtained with a cumulant method that can capture strong e-ph coupling, exhibit broad quasiparticle peaks with a small spectral weight (Z≈0.25) and pronounced LO-phonon sidebands characteristic of polaron effects. Our calculations predict features observed in photoemission spectra, including a 40-meV peak in the e-ph coupling distribution function not explained by existing models. These results show that the universal strong e-ph coupling found experimentally in lanthanum cuprates is an intrinsic feature of the parent compound, and elucidates its microscopic origin.