The giant barrel sponge Xestospongia is an ecologically important species that is widely distributed across the Indo-Pacific. Little is known, however, about the precise biogeographic distribution and the amount of morphological and genetic variation in this species. Here we provide the first detailed, fine-scaled (<200 km2) study of the morphological and genetic composition of X. testudinaria around Lembeh Island, Indonesia. Two mitochondrial (CO1 and ATP6 genes) and one nuclear (ATP synthase β intron) DNA markers were used to assess genetic variation. We identified four distinct morphotypes of X. testudinaria around Lembeh Island. These morphotypes were genetically differentiated with both mitochondrial and nuclear markers. Our results indicate that giant barrel sponges around Lembeh Island, which were all morphologically identified as X. testudinaria, consist of at least two different lineages that appear to be reproductively isolated. The first lineage is represented by individuals with a digitate surface area, CO1 haplotype C5, and is most abundant around the harbor area of Bitung city. The second lineage is represented by individuals with a predominantly smooth surface area, CO1 haplotype C1 and can be found all around Lembeh Island, though to a lesser extent around the harbor of Bitung city. Our findings of two additional unique genetic lineages suggests the presence of an even broader species complex possibly containing more than two reproductively isolated species. The existence of X. testudinaria as a species complex is a surprising result given the size, abundance and conspicuousness of the sponge.