Marine ecosystems serve as global carbon sinks and nutrient source or breeding ground for aquatic animals. Sponges are ancient parts of these important ecosystems and can be found in caves, the deep-sea, clear waters, or more turbid environments. Here, we studied the bacterial community composition of the calcareous sponge Clathrina clathrus sampled close to the island Corsica in the Mediterranean Sea with an emphasis on planctomycetes. We show that the phylum Planctomycetes accounts for 9% of the C. clathrus-associated bacterial community, a 5-fold enrichment compared to the surrounding seawater. Indeed, the use of C. clathrus as a yet untapped source of novel planctomycetal strains led to the isolation of strain KS4T. The strain represents a novel genus and species within the class Phycisphaerae in the phylum Planctomycetes and displays interesting cell biological features, such as formation of outer membrane vesicles and an unexpected mode of cell division.