Bacteria belonging to the Pseudoalteromonas genus have important ecological implications in marine environments, playing a role in the control of microbial community as producers of bioactive molecules endowed with antifouling activity and able to antagonize larvae, fungi and bacteria, including important human pathogens. For these reasons, representatives of this genus are very promising for biotechnological and biomedical applications. In this work, we used different genome-scale approaches to infer the taxonomy of 38 Pseudoalteromonas representatives (most of which isolated from Antarctica) and whose complete genome has been sequenced. We show that an accurate re-evaluation of the real taxonomic relationships of Pseudoalteromonas representatives is needed since many inconsistencies with the current taxonomic annotation were observed. Moreover, data obtained with different genome-scale methods are consistent, confirming the reliability of the genomic approaches. On the basis of these data, we propose a re-annotation for some Pseudoalteromonas species. This proposal should be validated in the future by comparing the phenotypes of these strains.