Spatial priorities for the conservation of three key Mediterranean habitats, i.e. seagrass Posidonia oceanica meadows, coralligenous formations, and marine caves, were determined through a systematic planning approach. Available information on the distribution of these habitats across the entire Mediterranean Sea was compiled to produce basin-scale distribution maps. Conservation targets for each habitat type were set according to European Union guidelines. Surrogates were used to estimate the spatial variation of opportunity cost for commercial, non-commercial fishing, and aquaculture. Marxan conservation planning software was used to evaluate the comparative utility of two planning scenarios: (a) a whole-basin scenario, referring to selection of priority areas across the whole Mediterranean Sea, and (b) an ecoregional scenario, in which priority areas were selected within eight predefined ecoregions. Although both scenarios required approximately the same total area to be protected in order to achieve conservation targets, the opportunity cost differed between them. The whole-basin scenario yielded a lower opportunity cost, but the Alboran Sea ecoregion was not represented and priority areas were predominantly located in the Ionian, Aegean, and Adriatic Seas. In comparison, the ecoregional scenario resulted in a higher representation of ecoregions and a more even distribution of priority areas, albeit with a higher opportunity cost. We suggest that planning at the ecoregional level ensures better representativeness of the selected conservation features and adequate protection of species, functional, and genetic diversity across the basin. While there are several initiatives that identify priority areas in the Mediterranean Sea, our approach is novel as it combines three issues: (a) it is based on the distribution of habitats and not species, which was rarely the case in previous efforts, (b) it considers spatial variability of cost throughout this socioeconomically heterogeneous basin, and (c) it adopts ecoregions as the most appropriate level for large-scale planning.