We elucidate the nature of the electron-phonon interaction in the archetypal hybrid perovskite CH₃NH₃PbI₃ using ab initio many-body calculations and an exactly solvable model. We demonstrate that electrons and holes near the band edges primarily interact with three distinct groups of longitudinal-optical vibrations, in order of importance: the stretching of the Pb-I bond, the bending of the Pb-I-Pb bonds, and the libration of the organic cations. These polar phonons induce ultrafast intraband carrier relaxation over timescales of 6–30 fs and yield polaron effective masses 28% heavier than the bare band masses. These findings allow us to rationalize previous experimental observations and provide a key to understanding carrier dynamics in halide perovskites.