Marine protected areas (MPAs) are major tools to protect biodiversity and sustain fisheries. For species with a sedentary adult phase and a dispersive larval phase, the effectiveness of MPA networks for population persistence depends on connectivity through larval dispersal. However, connectivity patterns between MPAs remain largely unknown at large spatial scales. Here, we used a biophysical model to evaluate connectivity between MPAs in the Mediterranean Sea, a region of extremely rich biodiversity that is currently protected by a system of approximately a hundred MPAs. The model was parameterized according to the dispersal capacity of the dusky grouper Epinephelus marginatus, an archetypal conservation-dependent species, with high economic importance and emblematic in the Mediterranean. Using various connectivity metrics and graph theory, we showed that Mediterranean MPAs are far from constituting a true, well-connected network. On average, each MPA was directly connected to four others and MPAs were clustered into several groups. Two MPAs (one in the Balearic Islands and one in Sardinia) emerged as crucial nodes for ensuring multi-generational connectivity. The high heterogeneity of MPA distribution, with low density in the South-Eastern Mediterranean, coupled with a mean dispersal distance of 120 km, leaves about 20% of the continental shelf without any larval supply. This low connectivity, here demonstrated for a major Mediterranean species, poses new challenges for the creation of a future Mediterranean network of well-connected MPAs providing recruitment to the whole continental shelf. This issue is even more critical given that the expected reduction of pelagic larval duration following sea temperature rise will likely decrease connectivity even more.