This study focuses on the population genetic structure of the green crab Carcinus aestuarii along part of the African Mediterranean coast, with the main target to confirm genetic subdivision across the well documented genetic boundary of the Siculo-Tunisian Strait. For this purpose, the mitochondrial COI (cytochrome oxidase I) gene and five polymorphic microsatellite loci were analysed in 144 and 120 specimens, respectively. Our results show the existence of two distinct haplogroups, separated by 16 mutational steps and revealed a non random distribution of the genetic variation along the African Mediterranean coast. Dating analyses, based on the use of different molecular clock models and rates, placed the divergence among both haplogroups at 1.91 Myr (95% HPD: 1.11–2.68 Myr) to 0.69 Myr (95% HPD: 0.44–0.98 Myr). This range of divergence time estimation corresponds to the Early Pleistocene. The particular pattern of genetic divergence among Eastern and Western African Mediterranean populations of C. aestuarii, detected by 2-level AMOVA at the mitochondrial level, was consistent with that inferred from microsatellite analysis and suggests a vicariant event in C. aestuarii. Demographic reconstruction, inferred from mismatch distribution and BSP analyses, yielded different patterns of demographic history between both African Mediterranean groups. The distribution pattern of the two haplogroups across the African Mediterranean coast, along with results of Bayesian analysis of genetic structure revealing an intermediate geographic group between the two divergent groups of the African coast, support the hypothesis of a secondary contact between two historically isolated groups. Although this hypothetical contact zone, thought to be located near the Siculo-Tunisian Strait, still needs to be verified, the asymmetric gene flow from Western to Eastern African Mediterranean, as inferred by the results of a MIGRATE analysis, reinforces the previously mentioned results.