The role of electron-phonon scattering in finite-temperature anomalous Hall effect is still poorly understood. In this work, we present a Boltzmann theory for the side-jump contribution from electron-phonon scattering, which is derived from the microscopic quantum mechanical theory. We show that the resulting phonon side-jump conductivity generally approaches different limiting values in the high and low temperature limits, and hence can exhibit strong temperature dependence in the intermediate temperature regime. Our theory is amenable to ab initio treatment, which makes quantitative comparison between theoretical and experimental results possible.