In order to identify potential microorganisms with high denitrifying capacity from tannery wastewaters, 1000 pure cultures of bacterial isolates from Modjo Tannery Pilot and Ethio-tannery wastewater treatment plants (WWTP), in Ethiopia, were investigated. Twenty-eight isolates were selected as efficient denitrifiers. These were Gram-negative rods, oxidase and catalase positive denitrifying organisms. The 28 denitrifying strains were further classified according to their biochemical fingerprints into three different phylogenetic groups (BPT1, BPT2 and BPT3) and seven singles. Isolates B79T, B11, B12, B15, B28 and B38 belonging to the BPT3 cluster were found to be the most efficient denitrifying bacteria. All phenotypic studies, including cellular fatty acid profiles, showed that the 6 BPT3 isolates were closely related to each other. The 16S rRNA partial sequence analysis of type strain B79T (CCUG 45880) indicated a sequence similarity of 99% to Brachymonas denitrificans JCM9216 (D14320) in the β-subdivision of proteobacteria. Further studies of the effects of chromium III and sulphide on the six Brachymonas denitrificans strains indicated that denitrification by the isolates were inhibited 50% at concentrations of 54 and 96 mg/l, respectively. The efficient isolates characterized in this study are of great value because of their excellent denitrifying properties and relatively high tolerance to the concentrations of toxic compounds (70 mg chromium/l and 160 mg sulphide/l) prevailing in tannery wastewaters.