The European Union has made extensive biodiversity conservation efforts with the Habitats and Birds Directives and with the establishment of the Natura 2000 network of protected areas, one of the largest networks of conservation areas worldwide. We performed a gap analysis of the entire Natura 2000 system plus national protected areas and all terrestrial vertebrates (freshwater fish excluded). We also evaluated the level of connectivity of both systems, providing therefore a first estimate of the functionality of the Natura 2000 system as an effective network of protected areas. Together national protected areas and the Natura 2000 network covered more than one-third of the European Union. National protected areas did not offer protection to 13 total gap species (i.e., species not covered by any protected area) or to almost 300 partial gap species (i.e., species whose representation target is not met). Together the Natura 2000 network and national protected areas left 1 total gap species and 121 partial gap species unprotected. The terrestrial vertebrates listed in the Habitats and Birds Directives were relatively well covered (especially birds), and overall connectivity was improved considerably by Natura 2000 sites that act as stepping stones between national protected areas. Overall, we found that the Natura 2000 network represents at continental level an important network of protected areas that acts as a good complement to existing national protected areas. However, a number of problems remain that are mainly linked to the criteria used to list the species in the Habitats and Birds Directives. The European Commission initiated in 2014 a process aimed at assessing the importance of the Birds and Habitats Directives for biodiversity conservation. Our results contribute to this assessment and suggest the system is largely effective for terrestrial vertebrates but would benefit from further updating of the species lists and field management.