A Gram-negative, non-motile, rod shaped, and orange-pigmented chemoheterotrophic bacterium, strain $MS-31^T$ was isolated from the marine sponge Hymeniacidon flavia, collected from near Jeju Island, Korea. The Strain $MS-31^T$ was subjected to a polyphasic taxonomic study. The phylogenetic analysis based on the 16S rRNA gene sequences revealed that the novel isolate could be affiliated within the genus Sphingomonas. The strain $MS-31^T$ showed 95.6% of 16S rRNA gene sequence similarity with the most closely related species Sphingomonas koreensis $JSS26^T$. The DNA G+C content of the strain $MS-31^T$ was 69.4 mol%. The major isoprenoid quinone was ubiqunone 10 and predominant cellular fatty acids were summed feature 7 (comprising $C_{18:1}$ ${omega}7c$, $C_{18:1}$ ${omega}9t$ and/or $C_{18:1}$ ${omega}12t$, 39.7%), $C_{16:0}$ (16.3%), $C_{14:0}$ 2OH (15.9%) and summed feature 3 (comprising $C_{16:1}$ ${omega}7c$ and/or $C_{15:0}$ iso 2OH, 11.7%). The polar lipids were sphingoglycolipid, phosphatidylethanolamine, phosphatidylglycerol, diphosphatidylglycerol and unidentified glycolipid. Based on the evidence from the polyphasic taxonomic study, the strain should be classified as a new species of the genus Sphingomonas. As a result, the name Sphingomonas jejuensis sp. nov. (type strain $MS-31^T$ =KCTC $23321^T$ =NBRC $107775^T$) is proposed.