Here, we report the draft genome sequence of Sphingorhabdus sp. strain EL138, an alphaproteobacterium that shows potential to degrade polycyclic aromatic compounds and to cope with various heavy metals and antibiotics. Moreover, the strain, isolated from the gorgonian coral Eunicella labiata, possesses several genes involved in the biosynthesis of polyphosphates, polyketides, and terpenoids.