The pairs of nitrogen fixation genes nifDK and nifEN encode for the alpha and beta subunits of nitrogenase and for the two subunits of the NifNE protein complex, involved in the biosynthesis of the FeMo cofactor, respectively. Comparative analysis of the amino acid sequences of the four NifD, NifK, NifE, and NifN in several archaeal and bacterial diazotrophs showed extensive sequence similarity between them, suggesting that their encoding genes constitute a novel paralogous gene family. We propose a two-step model to reconstruct the possible evolutionary history of the four genes. Accordingly, an ancestor gene gave rise, by an in-tandem paralogous duplication event followed by divergence, to an ancestral bicistronic operon; the latter, in turn, underwent a paralogous operon duplication event followed by evolutionary divergence leading to the ancestors of the present-day nifDK and nifEN operons. Both these paralogous duplication events very likely predated the appearance of the last universal common ancestor. The possible role of the ancestral gene and operon in nitrogen fixation is also discussed.