Rada Europejska wybrała w 2004 r. na siedzibę Frontexu Warszawę na fali entuzjazmu do ledwo co przeprowadzonego poszerzenia Unii na Wschód. Samo powstanie nowej instytucji wynikało jednak z czegoś innego: masowego napływu imigrantów na Wyspy Kanaryjskie dwa lata wcześniej. Kraje bogatej Północy, do których dociera większość nielegalnych imigrantów, chciały w ten sposób uzyskać kontrolę nad ochroną granic zewnętrznych Unii.
Początkowo był to jednak niewiele więcej niż symbol. Jeszcze w 2014 r. budżet agencji zamykał się skromną kwotą 100 mln euro. Świeżo po utworzeniu wspólnej waluty w większości unijnych stolic nie było chęci do pozbywania się kompetencji w kolejnym kluczowym dla suwerenności obszarze: ochrony granic.