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 M1T, 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 M1T 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 M1T 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 M1T 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 M1T from related pseudomonads. Based on the evidence of this polyphasic taxonomic study, strain M1T represents a novel species, for which the name Pseudomonas deceptionensis sp. nov. is proposed. The type strain is M1T ( = LMG 25555T = CECT 7677T).