We have made a comprehensive study of the denitrifying species of the genus Halomonas, evaluating both the phylogenetic and phenotypic relationships amongst them and other species of Halomonas. The phylogenetic analysis was based on the 16S rRNA gene sequence as well as those of the three genes essential to a complete denitrification process: narH, nirS and nosZ. The main aim of the phenotypic study was to improve our knowledge of some of the species in question. To this end we investigated the type strain of each species, although in the case of Halomonas cerina we also studied strains R53 and 15CR. In addition to this we investigated some other strains phylogenetically related to Halomonas ventosae, Halomonas denitrificans and Halomonas koreensis that were isolated during this study. We also looked into the conditions under which all these bacteria denitrify. Our results indicate that these denitrifying species of Halomonas are all closely related. A numerical analysis of the phenotypic data demonstrates a high phenotypic similarity (73%) between most of them. In addition, all the denitrifying strains have a high G+C content of between 63 and 74.3 mol%. The results of the phylogenetic study point to two evolutionary lineages for the process. Although phenotypic similarity does not always reflect phylogenetic relatedness, we have found significant congruence between both features in Halomonas, making it clear that denitrifying ability should be considered as an important phenotypic and phylogenetic discriminatory marker within this genus.