Isolated marine protected areas (MPAs) may not be enough to sustain viable populations of marine species, particularly the many small coastal MPAs which resulted due to social, economic and political constraints. Properly designed MPA networks can circumvent such limitations due to their potential synergistic positive effects, but this crucial step is frequently obstructed by lack of baseline ecological information. In this paper, we use systematic conservation planning on European Nature Information System coastal habitat information available for Portugal to demonstrate how an ecologically coherent nation-wide MPA network can be designed. We used the software Marxan to obtain near optimal solutions for each of three pre-determined conservation targets (10%, 30% and 50% protection) while maintaining the cost of including conservation units as low as possible. Marxan solutions were subsequently optimized with MinPatch by keeping each MPA above a minimum size that reflects the existing information on habitat use by some key marine fishes. Results show that 10% protection for all habitats would only require a relatively small increase in the number (from 6 to 10) and area (from 479 km2 to 509 km2) of already existing MPAs in mainland Portugal whereas substantial increases would be required to achieve the 50% target. This rather simple approach offers the added benefit of allowing design improvement as more relevant ecological information becomes available, including deeper habitat mapping across the whole continental shelf, allowing a coherent, adaptive and inclusive optimal MPA network to be designed.