Em 2004 foi criada a Agência Europeia de Gestão da Cooperação Operacional nas Fronteiras Externas dos Estados-Membros da UE, com sede em Varsóvia (Polónia), tendo em vista uma gestão integrada das fronteiras externas dos Estados-Membros da União. Cabendo aos Estados-Membros a responsabilidade pelo controlo e vigilância das fronteiras externas, esta agência, denominada FRONTEX (provém do francês: Frontières extérieures), tem como objetivo reforçar a segurança nas fronteiras, facilitando e tornando mais eficaz a aplicação das disposições comunitárias relativas à gestão das fronteiras externas e assegurando a coordenação das ações dos Estados-Membros na aplicação dessas disposições. Esta preocupação comunitária resulta da evidência que a fraqueza no controlo num Estado terá efeitos inevitáveis sobre a segurança de todos os demais Estados-Membros (consequência da livre circulação sem fronteiras internas entre os Estados-Membros).
A sua ação desenvolvia-se em quatro vertentes complementares: medidas operacionais com e em Estados terceiros; cooperação operacional ao nível da segurança das fronteiras com países vizinhos; controlos fronteiriços e vigilância das fronteiras externas; e medidas complementares de segurança das fronteiras nos Estados-Membros.
Entrou em funcionamento a 1 de maio de 2005.
Viu o seu papel reforçado logo em 2007, com a criação das equipas de intervenção rápida nas fronteiras, chamados "RABITS” (do inglês "RApid Border Intervention TeamS”), cujo principal objetivo era aumentar a capacidade e rapidez da Agência na assistência operacional aos Estados-Membros, em particular quando sujeitos a uma particular pressão nas fronteiras externas sob sua jurisdição. Estas equipas foram solicitadas pela primeira vez, em outubro de 2010, pela Grécia. À época, a fronteira terrestre com a Turquia verificava um crescente e elevado número de passagens ilegais.
Em 2011, já com movimentos migratórios provocados pela primavera Árabe a fazerem sentir-se no continente europeu, a agência viu novamente – e de maneira significativa – o seu papel reforçado: mais competências, incluindo de coordenação, no âmbito de operações conjuntas com Estados-Membros; possibilidade de adquirir equipamento próprio; mais competências operacionais; reforço do mecanismo de controlo dos direitos fundamentais, incluindo o principio de non-refoulement; maior cooperação com demais agências, nomeadamente EUROPOL e EASO.
Em 2013, a Agência torna-se responsável pelo estabelecimento, manutenção e coordenação do sistema EUROSUR.
Por fim, em 2014, e depois de um processo bastante contencioso, o Deputado ao Parlamento Europeu Carlos Coelho, conseguiu fazer aprovar um instrumento que veio regular a interceção de barcos no mar, o desembarque e as operações de busca e salvamento durante as operações conjuntas da Frontex. No fundo, em reflexo das crescentes competências operacionais da Agência e já com fluxos migratórios no Mediterrâneo bastante acentuados, foi introduzida a obrigação de salvar todos aqueles que fossem encontrados em apuros no Mar e de respeitar a obrigação internacional de não-repulsão.
Em 2016, em resposta e já no pico da crise migratória que afetou a União Europeia, em particular Itália e Grécia, a Frontex conheceu a sua maior transformação, sendo substituída pela Agência Europeia de Fronteiras e Costeira.