Solar cells and optoelectronic devices are exposed to heat that degrades performance. Therefore, elucidating temperature-dependent charge carrier dynamics is essential for device optimization. Charge carrier lifetimes decrease with temperature in conventional semiconductors. The opposite, anomalous trend is observed in some experiments performed with MAPbI3 (MA = CH3NH3+) and other metal halide perovskites. Using ab initio quantum dynamics simulation, we establish the atomic mechanisms responsible for nonradiative electron-hole recombination in orthorhombic-, tetragonal-, and cubic MAPbI3. We demonstrate that structural disorder arising from the phase transitions is as important as the disorder due to heating in the same phase. The carrier lifetimes grow both with increasing temperature in the same phase and upon transition to the higher-temperature phases. The increased lifetime is rationalized by structural disorder that induces partial charge localization, decreases nonadiabatic coupling, and shortens quantum coherence. Inelastic and elastic electron-vibrational interactions exhibit opposite dependence on temperature and phase. The partial disorder and localization arise from thermal motions of both the inorganic lattice and the organic cations and depend significantly on the phase. The structural deformations induced by thermal fluctuations and phase transitions are on the same order as deformations induced by defects, and hence, thermal disorder plays a very important role. Since charge localization increases carrier lifetimes but inhibits transport, an optimal regime maximizing carrier diffusion can be designed, depending on phase, temperature, material morphology, and device architecture. The atomistic mechanisms responsible for the enhanced carrier lifetimes at elevated temperatures provide guidelines for the design of improved solar energy and optoelectronic materials.