The current situation in Ukraine, on the one hand, and the issue of migration from different regions of the Middle East and North Africa, on the other, bring into light an unstable state of affairs with respect to the EU’s Neighbourhood security. This comes at a time when the EU is rethinking its greater purpose in the region and around the world. This paper aims to identify the cooperation gaps between the EU and NATO, concluding with a set of policy proposals aimed at dissolving the current limitations of the EU-NATO relationship.