The interaction between electrons and lattice vibrations determines key physical properties of materials, including their electrical and heat transport, excited electron dynamics, phase transitions, and superconductivity. We present a new ab initio method that employs atomic orbital (AO) wavefunctions to compute the electron-phonon (e-ph) interactions in materials and interpolate the e-ph coupling matrix elements to fine Brillouin zone grids. We detail the numerical implementation of such AO-based e-ph calculations, and benchmark them against direct density functional theory calculations and Wannier function (WF) interpolation. The key advantages of AOs over WFs for e-ph calculations are outlined. Since AOs are fixed basis functions associated with the atoms, they circumvent the need to generate a material-specific localized basis set with a trial-and-error approach, as is needed in WFs. Therefore, AOs are ideal to compute e-ph interactions in chemically and structurally complex materials for which WFs are challenging to generate, and are also promising for high-throughput materials discovery. While our results focus on AOs, the formalism we present generalizes e-ph calculations to arbitrary localized basis sets, with WFs recovered as a special case.