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).