In this study, two strains (SCSIO 10187(T) and SCSIO 10197) were isolated from a sediment sample collected from the South China Sea and characterized by using a polyphasic approach. Growth was observed at 15-35 °C (optimum 28 °C) and pH 5.0-8.0 (optimum pH 6.0). Based on 16S rRNA gene sequence analysis, the strains were identified as members of the genus Rhodococcus. Phylogenetic analysis showed that the two strains clustered together and the 16S rRNA gene sequence similarities between them and other members of the genus Rhodococcus were 93.2-97.7 %. The menaquinone type was MK-8(H(2)). Major cellular fatty acids were C(16 : 0), C(18 : 1)ω9c, C(17 : 0), 10-methyl C(18 : 0), C(18 : 0), C(19 : 0) and C(17 : 1)ω8c. The polar lipids were diphosphatidylglycerol, phosphatidylethanolamine, phosphatidylinositol and phosphatidylinositol mannoside. The DNA G+C contents of strains SCSIO 10187(T) and SCSIO 10197 were 63.7 and 63.2 mol%, respectively. The combined genotypic and phenotypic data showed that the two strains represent a novel species of the genus Rhodococcus, for which the name Rhodococcus nanhaiensis is proposed; the type strain is SCSIO 10187(T) ( = DSM 45608(T) = CCTCC AB 2011024(T)), with SCSIO 10197 ( = DSM 45609 = CCTCC AB 2011025) as a reference strain.