This working paper explores the operational cooperation between Frontex, the European Border and Coast Guard agency, and NATO. Since 2016, these two disparate actors have started to cooperate in the Aegean Sea and the Mediterranean Sea after NATO’s involvement in countering irregular migration. The aims of this paper is to explore their role in addressing a non-traditional security challenge, namely irregular migration, which provided the basis for joining efforts and initiating their operational cooperation. The latter raises serious concerns about the future of both institutions and the adopted EU strategy to cope with the issue of migration. All these define a new EU-NATO security partnership that has the potential to reshape the content of the transatlantic cooperation.