We have assessed for the first time the phylogenetic relationships and biogeographic history of the crabs of the genus Maja that inhabit European coasts: M. brachydactyla, M. crispata, M. goltziana and M. squinado. Using mitochondrial markers, we have recovered a well-resolved phylogenetic tree that supports a single origin for the European species, most likely from an Indo-West Pacific ancestor during the Early Miocene. In this phylogeny, M. goltziana appears as the basal European species, with a sister lineage bifurcating into an Eastern Atlantic (M. brachydactyla) and a Mediterranean (M. crispata and M. squinado) clade. We propose the Tethyan Seaway as the initial colonization route, although an entrance through South Africa cannot be discounted. The Eastern Atlantic/Mediterranean split seems to predate the Messinian salinity crisis, which, in turn, could have promoted the recent divergence within the Mediterranean. In addition, Pleistocene glaciations could explain the current diversity in the Eastern Atlantic Ocean, where a unique mitochondrial lineage is found. According to this, the genetic profile of South African crabs appears to belong to M. brachydactyla, questioning the validity of the putative species M. capensis.