První zmínky o zřízení Úřadu evropského veřejného žalobce (European Public Prosecutor´s Office, EPPO) najdeme již v tzv. Corpus Iuris z roku 1997 a následně v jeho aktualizované verzi z roku 2002. Corpus Iuris byl svého času jakýmsi neformálním návrhem evropského trestního kodexu, respektive trestněprávní studií, která měla na evropské úrovni zajistit efektivnější ochranu finančních zájmů tehdejších Evropských společenství (ES). Evropští odborníci na trestní právo tehdy dokument rozdělili na dvě části.
První (hmotněprávní) část obsahovala mimo jiné skutkové podstaty „evropských“ trestných činů. Těch mělo být osm a zahrnovaly kupříkladu trestný čin podvodu, zpronevěry či korupci. Druhá část (procesněprávní) pak zahrnovala vytvoření nadnárodního Úřadu evropského veřejného žalobce, který by měl pravomoc a působnost oněch osm „evropských“ trestných činů, které poškozují nebo ohrožují finanční zájmy EU, vyšetřovat a trestně stíhat bez ohledu na národní hranice.
Snahy o přijetí Corpus Iuris ovšem nebyly úspěšné, dokument byl totiž na evropské úrovni, zejména pak v Evropském parlamentu, podroben značné kritice. Úspěšné nebyly ani snahy zakomponovat úřad do návrhu Smlouvy o Ústavě pro Evropu v roce 2004. Na myšlenku vytvoření úřadu se ale nezapomnělo. Právní základ pro jeho zřízení následně přinesla Lisabonská smlouva, která nabyla účinnosti v prosinci 2009. Smlouva o fungování Evropské unie (SFEU) od té doby obsahuje čl. 86 odst. 1, který zní:
„Pro boj proti trestným činům poškozujícím nebo ohrožujícím finanční zájmy Unie může Rada zvláštním legislativním postupem formou nařízení vytvořit z Eurojustu Úřad evropského veřejného žalobce. Rada rozhoduje jednomyslně po obdržení souhlasu Evropského parlamentu.“
Toho Evropská komise využila v roce 2013, kdy představila legislativní návrh nařízení, který by úřad vytvořil. Komise přitom argumentovala, že pro efektivní ochranu finančních zájmů EU – a tedy peněz evropských daňových poplatníků – je zřízení takového úřadu s nadnárodní pravomocí naprosto nezbytné.
Během legislativního procesu ale nastal problém. Úřad musí být zřízen zvláštním legislativním postupem, v Radě bylo proto třeba nalézt jednomyslnost. A to se nepovedlo. S tím však zmíněný čl. 86 odst. 1 SFEU počítá, když ve třetím pododstavci říká, že:
„Není-li dohody dosaženo a pokud si alespoň devět členských států přeje navázat posílenou spolupráci na základě dotčeného návrhu nařízení, oznámí to ve stejné lhůtě Evropskému parlamentu, Radě a Komisi. V takovém případě se povolení k zavedení posílené spolupráce podle čl. 20 odst. 2 Smlouvy o Evropské unii a čl. 329 odst. 1 této smlouvy považuje za udělené a použijí se ustanovení o posílené spolupráci.“
Toho členské státy také využily a rozhodly se zřídit Úřad evropského veřejného žalobce v rámci tzv. posílené spolupráce. Stalo se tak v dubnu 2017. Tehdy se posílené spolupráce rozhodlo zúčastnit 16 zemí (Belgie, Bulharsko, Chorvatsko, Kypr, Česká republika, Finsko, Francie, Německo, Řecko, Litva, Lucembursko, Portugalsko, Rumunsko, Slovensko, Slovinsko a Španělsko).
K této skupině se v následujících měsících rozhodly přidat i další země. Konkrétně pak Estonsko, Itálie, Lotyšsko a Rakousko, v srpnu 2018 se přidala i Malta a Nizozemí. V současné době se tedy posílené spolupráce účastní celkem 22 členských zemí EU. Mimo i nadále zůstávají Polsko, Maďarsko, Švédsko, Irsko a Dánsko. I tyto země se však mohou k úřadu v budoucnu kdykoli připojit.

Právním základem úřadu se stalo nařízení Rady 2017/1939 ze dne 12. října 2017, kterým se provádí posílená spolupráce za účelem zřízení Úřadu evropského veřejného žalobce. Tím však samotné vytváření úřadu teprve začalo. Až v červenci 2018 bylo na unijní úrovni přijato důležité prováděcí rozhodnutí Rady (EU) 2018/1696, které vytvořilo výběrovou komisi. Ta měla za úkol zúžit počet kandidátů na evropského nejvyššího žalobce na tři. Finální volbu z těchto tří kandidátů pak měla na starosti Rada společně s Evropským parlamentem. Následná jednání mezi těmito institucemi trvala řadu měsíců.
V září 2019 ale přišel zlom – členské státy se společně s Parlamentem dohodly, že historicky prvním evropským nejvyšším žalobcem se stane rumunská prokurátorka Laura Codruţa Kövesiová. Paradoxem celého výběrového řízení a vyjednávání bylo, že rumunskou kandidátku odmítala podpořit její vlastní vláda. Přesto se však nakonec toto jméno podařilo – i přes nesouhlas rumunské vlády – prosadit.
Kövesiová se funkce ujala v listopadu 2019 a ihned se pustila do personálního a finančního zabezpečení úřadu. Podle původních plánů jí k tomu má stačit jeden rok – úřad má být plně funkční a začít plnit své úkoly od listopadu 2020. Evropská nejvyšší žalobkyně však do té doby musí stihnout řadu úkolů, jako třeba vytvořit jednací řád úřadu, zajistit potřebné personální a technické zabezpečení úřadu, zřídit kolegium a stálé komory či dohlédnout na jmenování evropských pověřených žalobců v jednotlivých členských zemích.