Cryptic species are widespread across the phylum Porifera making the identification of non-indigenous species difficult, an issue not easily resolved by the use of morphological characteristics. The widespread order Haplosclerida is a prime example due to limited and plastic morphological features. Here, we study the reported introduction of Haliclona (Soestella) caerulea from the Caribbean to Palmyra Atoll via Hawai'i using morphological characteristics and genetic analyses based on one nuclear (18s rDNA) and three mitochondrial (COI, the barcoding COI extension (COI ext.) and rnl rDNA) markers. Despite no clear division in lengths of the oxea spicules between the samples, both mtDNA and nDNA phylogenetic trees supported similar topologies resolving two distinct clades. Across the two clades, the concatenated mtDNA tree resolved twelve subclades, with the COI ext. yielding most of the variability between the samples. Low sequence divergence values (0.68%) between two of the subclades indicate that the same species is likely to occur at Palmyra, Hawai'i and the Caribbean, supporting the hypothesis that H. caerulea was introduced to Palmyra from the Caribbean, although whether species came directly from the Caribbean to Palmyra or from Hawai'i remains unresolved. Conversely, the pattern of highly divergent cryptic species supports the notion that traditionally used spicule measurements are taxonomically unreliable in this group. This study illustrates how understanding the scale of within- as opposed to between-species level genetic variation is critical for interpreting biogeographic patterns and inferring the origins of introduced organisms.