Nonradiative electron-hole recombination plays a key role in determining photon conversion efficiencies in solar cells. Experiments demonstrate significant reduction in the recombination rate upon passivation of methylammonium lead iodide perovskite with Lewis base molecules. Using nonadiabatic molecular dynamics combined with time-domain density functional theory, we find that the nonradiative charge recombination is decelerated by an order of magnitude upon adsorption of the molecules. Thiophene acts by the traditional passivation mechanism, forcing electron density away from the surface. In contrast, pyridine localizes the electron at the surface while leaving it energetically near the conduction band edge. This is because pyridine creates a stronger coordinative bond with a lead atom of the perovskite and has a lower energy unoccupied orbital compared with thiophene due to the more electronegative nitrogen atom relative to thiophene's sulfur. Both molecules reduce two-fold the nonadiabatic coupling and electronic coherence time. A broad range of vibrational modes couple to the electronic subsystem, arising from inorganic and organic components. The simulations reveal the atomistic mechanisms underlying the enhancement of the excited-state lifetime achieved by the perovskite passivation, rationalize the experimental results, and advance our understanding of charge-phonon dynamics in perovskite solar cells.