La sua costruzione iniziò nel 72 sotto l'imperatore Vespasiano, della dinastia flavia. I lavori furono finanziati, come altre opere pubbliche del periodo, con il provento delle tasse provinciali e il bottino del saccheggio del tempio di Gerusalemme (70 d.C.).
L'area scelta era una vallata tra la Velia, il colle Oppio e il Celio, in cui si trovava un lago artificiale (lo stagnum citato dal poeta Marziale) fatto scavare da Nerone per la propria Domus Aurea.

Questo specchio d'acqua, alimentato da fonti che sgorgavano dalle fondazioni del Tempio del Divo Claudio sul Celio, venne ricoperto da Vespasiano con un gesto riparatorio contro la politica del tiranno Nerone che aveva usurpato il terreno pubblico, e destinato ad uso proprio, rendendo così evidente la differenza tra il vecchio ed il nuovo principato.

Vespasiano fece dirottare l'acquedotto per uso civile, bonificò il lago e vi fece gettare delle fondazioni, più resistenti nel punto in cui sarebbe dovuta essere edificata la cavea.

Vespasiano vide la costruzione dei primi due piani e riuscì a dedicare l'edificio prima della propria morte nel 79.[3] L'edificio era il primo grande anfiteatro stabile di Roma, dopo due strutture minori o provvisorie di epoca giulio-claudia (l'amphiteatrum Tauri e l'amphiteatrum Caligulae) e dopo ben 150 anni dai primi anfiteatri in Campania.

Il figlio e successore di Vespasiano, Tito, aggiunse il terzo e quarto ordine di posti e inaugurò l'anfiteatro con cento giorni di giochi, nell'80.[4] Poco dopo, il secondo figlio di Vespasiano, l'imperatore Domiziano, operò importanti modifiche, completando l'opera ad clipea (probabilmente degli scudi decorativi in bronzo dorato),[3], aggiungendo forse il maenarium summum[5] e realizzando i sotterranei dell'arena: dopo il completamento dei lavori non fu più possibile tenere nell'anfiteatro delle naumachie (rappresentazioni di battaglie navali), che invece le fonti riportano per l'epoca precedente.

Contemporaneamente all'anfiteatro vennero costruiti alcuni edifici di servizio per i giochi: i ludi (caserme e luoghi di allenamento per i gladiatori, tra cui sono noti il Magnus, il Gallicus, il Matutinus e il Dacicus), la caserma del distaccamento dei marinai della Classis Misenensis (la flotta romana di base a Miseno) adibiti alla manovra del velarium (castra misenatium), il summum choragium e gli armamentaria (depositi delle armi e delle attrezzature), il sanatorium (luogo di cura per le ferite dei combattimenti) e lo spoliarum un luogo in cui venivano trattate le spoglie dei gladiatori defunti in combattimento.