A yellow-coloured, Gram-stain-negative, non-motile, rod-shaped bacterium, designated K-1-16T, that is capable of degrading aliphatic hydrocarbons was isolated from oil-contaminated soil at Biratnagar, Morang, Nepal. It was able to grow at 15-45 °C, at pH 5.5-9.5 and with 0-5 % (w/v) NaCl. This strain was taxonomically characterized by a polyphasic approach. Based on 16S rRNA gene sequence analysis, strain K-1-16T belongs to the genus Sphingomonas and is closely related to Sphingomonas mucosissima CP173-2T (98.6 % similarity), Sphingomonas dokdonensis DS-4T (97.9 %), Sphingomonas faeni MA-olkiT (97.9 %), Sphingomonas aurantiaca MA101bT (97.8 %) and Sphingomonas xinjiangensis 10-1-84T (96.6 %). The predominant respiratory quinone was ubiquinone Q-10 and the major polyamine was homospermidine. The polar lipid profile revealed the presence of phosphatidylethanolamine, phosphatidylglycerol, diphosphatidylglycerol, phosphatidylcholine, phosphatidyldimethylethanolamine and sphingoglycolipid. The predominant fatty acids of strain K-1-16T were summed feature 8 (C18 : 1ω7c and/or C18 : 1ω6c), C16 : 0, summed feature 3 (C16 : 1ω7c and/or C16 : 1ω6c), C18 : 1ω7c 11-methyl and C14 : 0 2-OH. The genomic DNA G+C content was 64.8 mol%. Levels of DNA-DNA relatedness between strain K-1-16T and S. mucosissima DSM 17494T, S. dokdonensis KACC 17420T, S. faeni KCCM 41909T and S. aurantiaca KCCM 41908T were 49.7, 41.3, 43.7 and 36.7 %, respectively. The morphological, physiological, chemotaxonomic and phylogenetic analyses clearly distinguished this strain from its closest phylogenetic neighbours. Thus, strain K-1-16T represents a novel species of the genus Sphingomonas, for which the name Sphingomonas olei sp. nov. is proposed. The type strain is K-1-16T (=KEMB 9005-450T=KACC 19002T=JCM 31674T).