Conservation planning is crucial for megadiverse countries where biodiversity is coupled with incomplete reserve systems and limited resources to invest in conservation. Using Peru as an example of a megadiverse country, we asked whether the national system of protected areas satisfies biodiversity conservation needs. Further, to complement the existing reserve system, we identified and prioritized potential conservation areas using a combination of species distribution modeling, conservation planning and connectivity analysis. Based on a set of 2,869 species, including mammals, birds, amphibians, reptiles, butterflies, and plants, we used species distribution models to represent species' geographic ranges to reduce the effect of biased sampling and partial knowledge about species' distributions. A site-selection algorithm then searched for efficient and complementary proposals, based on the above distributions, for a more representative system of protection. Finally, we incorporated connectivity among areas in an innovative post-hoc analysis to prioritize those areas maximizing connectivity within the system. Our results highlight severe conservation gaps in the Coastal and Andean regions, and we propose several areas, which are not currently covered by the existing network of protected areas. Our approach helps to find areas that contribute to creating a more representative, connected and efficient network.