During the taxonomic investigation of cold-adapted bacteria from samples collected in the Antarctic area of the South Shetland Islands, one Gram-reaction-negative, psychrotolerant, aerobic bacterium, designated strain M1(T), was isolated from marine sediment collected on Deception Island. The organism was rod-shaped, catalase- and oxidase-positive and motile by means of a polar flagellum. This psychrotolerant strain grew at temperatures ranging from -4 °C to 34 °C. Phylogenetic studies based on 16S rRNA gene sequences confirmed that Antarctic isolate M1(T) was a member of the genus Pseudomonas and was located in the Pseudomonas fragi cluster. 16S rRNA gene sequence similarity values were >98 % between 13 type strains belonging to the Pseudomonas fluorescens lineage. However, phylogenetic analysis of rpoD gene sequences showed that strain M1(T) exhibited high sequence similarity only with respect to Pseudomonas psycrophila (97.42 %) and P. fragi (96.40 %) and DNA-DNA hybridization experiments between the Antarctic isolate M1(T) and the type strains of these two closely related species revealed relatedness values of 58 and 57 %, respectively. Several phenotypic characteristics, together with the results of polar lipid and cellular fatty acid analyses, were used to differentiate strain M1(T) from related pseudomonads. Based on the evidence of this polyphasic taxonomic study, strain M1(T) represents a novel species, for which the name Pseudomonas deceptionensis sp. nov. is proposed. The type strain is M1(T) ( = LMG 25555(T) = CECT 7677(T)).