To understand the phylogeny and taxonomy of eight new toluene-degrading denitrifying isolates, we performed a 16S rRNA sequence analysis and a gas chromatographic analysis of their cellular fatty acids and examined some of their biochemical and physiological features. These isolates had 16s rRNA sequence signatures identical to those of members of the beta subclass of the Proteobacteria. The levels of similarity were as follows: 97.9 to 99.9% among the new isolates; 91.2 to 92.4% between the new isolates and Azoarcus sp. strain S5b2; 95.3 to 96.2% between the new isolates and Azoarcus sp. strain BH72; and 94.8 to 95.3% between the new isolates and Azoarcus indigens VB32T (T = type strain). Phylogenetic trees constructed by using the distance matrix, maximum-parsimony, and maximum-likelihood methods showed that our eight denitrifying isolates form a phylogenetically coherent cluster which represents a sister lineage of the previously described Azoarcus species. Furthermore, the fatty acid profiles, the cell morphology, and several physiological and nutritional characteristics of the eight isolates and the previously described members of the genus Azoarcus were also similar. In contrast to the previously described members of the genus Azoarcus, the eight new isolates were capable of degrading toluene under denitrifying conditions. We concluded that these toluene-degrading denitrifiers are members of a new species of the novel nitrogen-fixing genus Azoarcus. We propose the name Azoarcus tolulyticus for these toluene-degrading denitrifying isolates and designate strain Tol-4 the type strain.