The American blue crab Callinectes sapidus is a particularly successful invader in estuarine ecosystems worldwide. Despite increasing awareness of its potential harm, the invasion history and underlying genetic diversity of this species within the Mediterranean Sea remain unknown. This study constitutes the first large-scale approach to study phylogeographic patterns of C. sapidus in Europe, facilitated by the first comparison of all currently available COI sequence data. For this investigation, 71 individuals of C. sapidus were newly analyzed and the entire COI gene was sequenced and used for a comparative phylogeographic analyses. For the first time, two separately used adjacent regions of this gene were combined in a single dataset. This allowed emphasizing the prevalence of three geographically defined lineages within the native range: (1) eastern North America, including the Gulf of Mexico, (2) the Caribbean, and (3) Brazil. New data from the Mediterranean reveal that non-native populations of C. sapidus are characterized by a conspicuously low genetic diversity (except for Turkey, where stocking took place), and that there is surprisingly low connectivity among established populations. The occurrence of strong genetic bottlenecks suggests few founder individuals. This confirms that, even under a scenario of restricted large-scale gene flow, a very limited number of invasive individuals is sufficient for a massive impact.