To construct an evolutionary hypothesis for the genus Frankia, gyrB (encoding gyrase B), nifH (encoding nitrogenase reductase) and glnII (encoding glutamine synthetase II) gene sequences were considered for 38 strains. The overall clustering pattern among Frankia strains based on the three analyzed sequences varied among themselves and with the previously established 16S rRNA gene phylogeny and they did not reliably reflect clear evolution of the four discerned Frankia clusters (1, 2, 3 and 4). Based on concatenated gyrB, nifH and glnII, robust phylogenetic trees were observed with the three treeing methods (Maximum Likelihood, Parsimony and Neighbor-Joining) and supported by strong bootstrap and posterior probability values (>75%) for overall branching. Cluster 4 (non-infective and/or non-nitrogen-fixing Frankia) was positioned at a deeper branch followed by cluster 3 (Rhamnaceae and Elaeagnaceae infective Frankia), while cluster 2 represents uncultured Frankia microsymbionts of the Coriariaceae, Datiscaceae, Rosaceae and of Ceanothus sp. (Rhamnaceae); Cluster 1 (Betulaceae, Myricaceae and Casuarinaceae infective Frankia) appears to have diverged more recently. The present study demonstrates the utility of phylogenetic analyses based upon concatenated gyrB, nifH and glnII sequences to help resolve previously unresolved or poorly resolved nodes and will aid in describing species among the genus Frankia.