A Gram-negative, non-motile, rod shaped, and orange-pigmented chemoheterotrophic bacterium, strain MS-31T was isolated from the marine sponge Hymeniacidon flavia, collected from near Jeju Island, Korea. The Strain MS-31T 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-31T showed 95.6% of 16S rRNA gene sequence similarity with the most closely related species Sphingomonas koreensis JSS26T. The DNA G+C content of the strain MS-31T was 69.4 mol%. The major isoprenoid quinone was ubiqunone 10 and predominant cellular fatty acids were summed feature 7 (comprising C18:1 ω7c, C18:1 ω9t and/or C18:1 ω12t, 39.7%), C16:0 (16.3%), C14:0 2OH (15.9%) and summed feature 3 (comprising C16:1 ω7c and/or C15: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-31T =KCTC 23321T =NBRC 107775T) is proposed.