Background: Small and cryptic sponges associated with cold-water coral reefs are particularly numerous and challenging to identify, but their ecological and biochemical importance is likely to compete with megabenthic specimens. Methodology/Principal Findings: Here we use a combination of the standard M1M6 and I3M11 partitions of the COI fragment, partial rDNA 28S sequences and morphology to delineate small encrusting Plocamionida species. In total, 46 specimens were retrieved from seven shallow to deep-water coral locations, crossing 3,000 km along the European margins. Our work provides evidence that the Plocamionida ambigua f. tylotata and f. grandichelata can be considered valid species, whereas Plocamionida ambigua f. tornata corresponds to the species P. ambigua. Within the monophyletic group of Plocamionida, P. microcionides is shown as really divergent from the other taxa, and four putative new Plocamionida species are suggested. Conclusions/Significance: This study shows that the use of molecular and morphological information in an integrative approach is a powerful tool for the identification of sponge species, and suggests that an under-estimated biodiversity of sponges occurs in cold-water coral reefs.