Lead bromide perovskites APbBr3 (A = Cs, MA, FA) hold great promise in optoelectronics and photovoltaics. Because the band gaps of the three materials are similar, and also because the A-site cation does not contribute to band edges, one would expect a minor influence of A-site cation on the excited-state lifetime of the perovskites. Experiments defy that expectation. By performing ab initio nonadiabatic (NA) molecular dynamics combined with time-domain density functional simulations, we demonstrate that the nonradiative electron-hole recombination times are in the order FAPbBr3 > MAPbBr3 > CsPbBr3, which are determined by the NA electron-phonon coupling because decoherence times are similar. The simulations show that the larger A-site cation and the smaller NA coupling because larger A-site cation suppresses the Pb-Br cages' motion. The electron-hole recombination is slow, ranging from subnanosecond to nanoseconds, because the NA coupling is small, less than 3 meV, and because decoherence time is slow, less than 7 fs. Both the trend of recombination and the time scales show excellent agreement with experiments. The time-domain atomistic simulations rationalize the experimental observations and advance our understanding of the cations' influence on perovskite excited-state lifetimes.