Strain Tibet-S9a3(T) was isolated from Qinghai-Tibet Plateau permafrost, China. The isolate was a Gram-negative, non-motile, non-spore-forming short rod. The 16S rRNA gene sequence indicated that strain Tibet-S9a3(T) was a member of the genus Paracoccus and was closely related to Paracoccus aestuarii B7(T) (98.2 % 16S rRNA gene sequence similarity), 'P. beibuensis' JLT1284 (97.9 %), P. homiensis DD-R11(T) (97.4 %), P. zeaxanthinifaciens ATCC 21588(T) (97.4 %) and other type strains of the genus (93.7-96.7 %). The G+C content of the genomic DNA was 69.1 mol% and the major isoprenoid quinone was ubiquinone-10. The major fatty acids were C18 : 1ω7c (87.6 %), C18 : 0 (4.3 %) and C10 : 0 3-OH (2.0 %). DNA-DNA relatedness between strain Tibet-S9a3(T) and P. aestuarii B7(T) was 37.9 %. On the basis of phenotypic and genotypic characteristics, it is suggested that strain Tibet-S9a3(T) represents a novel species of the genus Paracoccus, for which the name Paracoccus tibetensis sp. nov. is proposed. The type strain is Tibet-S9a3(T) ( = CGMCC 1.8925(T) = NBRC 105667(T)).