The anaerobic ammonium oxidation (anammox) bacteria can transform ammonium and nitrite to dinitrogen gas, and this obligate anaerobic process accounts for up to half of the global nitrogen loss in surface environments. Yet its origin and evolution, which may give important insights into the biogeochemistry of early Earth, remain enigmatic. Here, we performed a comprehensive phylogenomic and molecular clock analysis of anammox bacteria within the phylum Planctomycetes. After accommodating the uncertainties and factors influencing time estimates, which include implementing both a traditional cyanobacteria-based and a recently developed mitochondria-based molecular dating approach, we estimated a consistent origin of anammox bacteria at early Proterozoic and most likely around the so-called Great Oxidation Event (GOE; 2.32-2.5 Ga) which fundamentally changed global biogeochemical cycles. We further showed that during the origin of anammox bacteria, genes involved in oxidative stress adaptation, bioenergetics, and anammox granules formation were recruited, which might have contributed to their survival on an increasingly oxic Earth. Our findings suggest the rising levels of atmospheric oxygen, which made nitrite increasingly available, was a potential driving force for the emergence of anammox bacteria. This is one of the first studies that link the GOE to the evolution of obligate anaerobic bacteria.