A Gram-staining-negative, aerobic, light brown pigment bacterium, designated strain CE80T was isolated from marine sponge Callyspongia elegans in Jeju Island, Republic of Korea. Strain CE80T grew optimally at 25°C, in the range of pH 5.0-11.0 (optimum 7.0-8.0), and with 1.0-5.0% NaCl (optimum 1-3% (w/v)). Phylogenetic analysis based on the 16S rRNA gene sequence showed that strain CE80T belonged to the genus Labrenzia and was closely related to L. suaedae YC6927T (98.3%), L. alexandrii DFL-11T (96.6%), L. aggregata IAM 12614T (96.6%) L. marina mano18T (96.5%) and L. alba CECT 5094T (96.2%). The major fatty acids of strain CE80T were C18:1 ω7c, and summed feature. The polar lipids were diphosphatidylglycerol, phosphatidylcholine, phosphatidylethanolamine, phosphatidylglycerol, phosphatidylmonomethylethanolamin, one unidentified aminolipid, one phospholipid and four unidentified lipids. The DNA G+C content of strain CE80T was 55.9 mol%. The major respiratory quinone was Q-10. DNA-DNA relatedness between strain CE80T and L. suaedae YC6927T was 56.1±2.8%. On the basis of physiological and biochemical characterization and phylogenetic and chemotaxonomic analysis, strain CE80T represents a novel species of the Labrenzia, for which the name Labrenzia callyspongiae sp. nov., is proposed. The type strain is CE80T (=KCTC 42849T =JCM 31309T).