Advances in perovskite solar cells require development of means to control and eliminate the nonradiative charge recombination pathway. Using ab initio nonadiabatic molecular dynamics, we demonstrate that charge recombination in perovskites is extremely sensitive to the charge state of the halogen vacancy. A missing iodine anion in MAPbI3 has almost no effect on charge losses. However, when the vacancy is reduced, the recombination is accelerated by up to 2 orders of magnitude. The acceleration occurs due to formation of a deep hole trap in the singly reduced vacancy, and both deep and shallow hole traps for the doubly reduced vacancy. The shallow hole involves a significant rearrangement of the Pb-I lattice, leading to a new chemical species: a Pb-Pb dimer bound by the vacancy charge, and under-coordinated iodine bonds. Hole trapping by the singly reduced iodide vacancy operates parallel to recombination of free electron and hole, accelerating charge losses by a factor of 5. The doubly reduced vacancy acts by a sequential mechanism-free hole, to shallow trap, to deep trap, to free electron, and accelerates the recombination by a factor of 50. The study demonstrates that iodine anion vacancy can be beneficial to the performance, because it causes minor changes to the charge carrier lifetime, while increasing charge carrier concentration. However, the neutral iodine and iodine cation vacancies should be strongly avoided. The detailed insights into the charge carrier trapping and relaxation mechanisms provided by the simulation are essential for development of efficient photocatalytic, photovoltaic, optoelectronic and related devices.