Ammonia-oxidizing archaea (AOA) are chemolithoautotrophs that dominate nitrification in today’s low ammonium ocean, playing critical roles in the global nitrogen cycle, alongside ammonia-oxidizing bacteria (AOB) that favor higher ammonium environments. Nitrification may have occurred soon after the origin of oxygenic photosynthesis and provided fundamental nutrients for the emergence of eukaryotic organisms in the Proterozoic; however, the timing of biological evidence remains unclear. Here we show using phylogenetic models that AOA occurred ~1,165 (1,928-880) Mya in a terrestrial geothermal environment, ~652 (767-554) Mya in low temperature soil niches, and ~509 (629-412) Mya in aquatic environments. AOA originated in marine settings around 362 (478-274) Mya, which was followed by the rapid diversification of shallow- and deep- subgroups around 315 (478-207) Mya and 309 (460-207) Mya, respectively, leading to today’s domination of AOA in global oceans. The radiation of thermophilic AOA into mesophilic terrestrial soil may have been triggered by the 'snowball Earth' events of the Cryogenian Period and their 'hothouse Earth' aftermaths. The radiation of AOA into the deep ocean had to await the persistent oxygenation of the deep ocean that was associated with the rise of land plants. Our genetic analyses integrated with a geochemical data and a modeling framework offers an intriguing linkage between microbial evolution and the belated oxygenation of the deep ocean in the Paleozoic Era.