The evolutionary history of nitrogen fixation has been vigorously debated for almost two decades. Previous phylogenetic analyses of nitrogen fixation genes (nif) have shown support for either evolution by vertical descent or lateral transfer, depending on the specific nif gene examined and the method of analyses used. The debate centers on the placement and monophyly of the cyanobacteria, proteobacteria, and Gram-positive bacteria (actinobacteria and firmicutes). Some analyses place the cyanobacteria and actinobacteria within the proteobacteria, which suggests that the nif genes have been laterally transferred since this topology is incongruent with ribosomal phylogenies, the standard marker for comparison. Other nif analyses resolve and support the monophyly of the cyanobacteria, proteobacteria, and actinobacteria, supporting vertical descent. We have revisited these conflicting scenarios by analyzing nifD from an increased number of cyanobacteria, proteobacteria, and Gram-positive bacteria. Parsimony analyses of amino acid sequences and maximum likelihood analysis of nucleic acid sequences support the monophyly of the cyanobacteria and actinobacteria but not the proteobacteria, lending support for vertical descent. However, distance analysis of nucleic acid sequences placed the actinobacteria within the proteobacteria, supporting lateral transfer. We discuss evidence for both vertical descent and lateral transfer of nitrogen fixation.