The nitrogen fixation (nif) genes of nodule-forming Bradyrhizobium strains are generally located on symbiosis islands or symbiosis plasmids, suggesting that these genes have been transferred laterally. The nif genes of rhizobial and non-rhizobial Bradyrhizobium strains were compared in order to infer the evolutionary histories of nif genes. Based on all codon positions, the phylogenetic tree of concatenated nifD and nifK sequences showed that nifDK on symbiosis islands formed a different clade from nifDK on non-symbiotic loci (located outside of symbiosis islands and plasmids) with elongated branches; however, these genes were located in close proximity, when only the 1st and 2nd codon positions were analyzed. The guanine (G) and cytosine (C) content of the 3rd codon position of nifDK on symbiosis islands was lower than that on non-symbiotic loci. These results suggest that nif genes on symbiosis islands were derived from the non-symbiotic loci of Bradyrhizobium or closely related strains and have evolved toward a lower GC content with a higher substitution rate than the ancestral state. Meanwhile, nifDK on symbiosis plasmids clustered with nifDK on non-symbiotic loci in the tree representing all codon positions, and the GC content of symbiotic and non-symbiotic loci were similar. These results suggest that nif genes on symbiosis plasmids were derived from the non-symbiotic loci of Bradyrhizobium and have evolved with a similar evolutionary pattern and rate as the ancestral state.