The ongoing exploration of deep-water coral habitats in the Mediterranean Sea provides continuously new and original information on such bathyal habitats and their biodiversity. The MARCOS (Malta StRait of Sicily CORals) cruise conducted in the Strait of Sicily in springtime 2007 sampled, among other things, a number of sponges associated with coral banks off Linosa Island and south of Malta and, subordinately, with maerl beds at shallower depths. Twenty species belonging to Demospongiae (19) and Hexactinellida (one) are here listed. Two species are first records for the Mediterranean Sea while two are new additions to the Italian sponge fauna. Finally, three taxa are recorded for the first time associated with Mediterranean deep-water corals.