Hemoglobins are ubiquitous in Eukarya and Bacteria but, until now, have not been found in Archaea. A phylogenetic analysis of the recently revealed microbial family of globin-coupled heme-based sensors suggests that these sensors descended from an ancient globin-only progenitor, or a protoglobin (Pgb). Here, we report the discovery and characterization of two Pgbs from the Archaea: ApPgb from the obligately aerobic hyperthermophile Aeropyrum pernix, and MaPgb from the strictly anaerobic methanogen Methanosarcina acetivorans. Both ApPgb and MaPgb bind molecular oxygen, nitric oxide, and carbon monoxide by means of a heme moiety that is coordinated to the protein through the F8 histidine (histidine 120). We postulate that these archaeal globins are the ancestors of contemporary hemoglobins.