Leghemoglobins enable the endosymbiotic fixation of molecular nitrogen (N2) in legume nodules by channeling O2 for bacterial respiration while maintaining a micro-oxic environment to protect O2-sensitive nitrogenase. We found that the NIN-like protein (NLP) transcription factors NLP2 and NIN directly activate the expression of leghemoglobins through a promoter motif, resembling a “double” version of the nitrate-responsive elements (NREs) targeted by other NLPs, that has conserved orientation and position across legumes. CRISPR knockout of the NRE-like element resulted in strongly decreased expression of the associated leghemoglobin. Our findings indicate that the origins of the NLP-leghemoglobin module for O2 buffering in nodules can be traced to an ancient pairing of NLPs with nonsymbiotic hemoglobins that function in hypoxia.