Assessing the enormous diversity of Southern Ocean benthic species and their evolutionary histories is a central task in the era of global climate change. Based on mitochondrial markers, it was recently suggested that the circumpolar giant sea spider Colossendeis megalonyx comprises a complex of at least six cryptic species with mostly small and non-overlapping distribution ranges. Here, we expand the sampling to include over 500 mitochondrial COI sequences of specimens from around the Antarctic. Using multiple species delimitation approaches, the number of distinct mitochondrial OTUs increased from six to 15-20 with our larger dataset. In contrast to earlier studies, many of these clades show almost circumpolar distributions. Additionally, analysis of the nuclear internal transcribed spacer region for a subset of these specimens showed incongruence between nuclear and mitochondrial results. These mito-nuclear discordances suggest that several of the divergent mitochondrial lineages can hybridize and should not be interpreted as cryptic species. Our results suggest survival of C. megalonyx during Pleistocene glaciations in multiple refugia, some of them probably located on the Antarctic shelf, and emphasize the importance of multi-gene datasets to detect the presence of cryptic species, rather than their inference based on mitochondrial data alone.