Costa-Gavras nasce a Loutra Iraias, una circoscrizione dell'ex comune greco di Iraia (accorpato infatti, nel 2011, a quello di Gortyna), nel Peloponneso, nel 1933. Trasferitosi stabilmente in Francia nel 1952, della quale ne otterrà poi la cittadinanza, inizia dirigendo film polizieschi, per poi dedicarsi al genere del thriller/giallo politico per il resto della sua carriera (con qualche sortita, specie negli anni più recenti, nel dramma sociale), spesso affiancato dallo sceneggiatore spagnolo, espatriato pure lui, Jorge Semprún. Nel 1965 gira il thriller Vagone letto per assassini con Yves Montand, che diventa uno degli attori preferiti dal regista e che compare in tutte le sue pellicole girate in Europa.
Nel 1973 esce L'Amerikano, che denuncia l'appoggio dato dagli USA ai regimi autoritari del Sudamerica. Il film fu sceneggiato da Franco Solinas, ispiratosi alla vicenda di Anthony Dan Mitrione, ex capo della polizia di Richmond divenuto per conto della CIA "consigliere" USA di varie polizie sudamericane, il quale venne rapito e ucciso dai guerriglieri in Uruguay. Le riprese si svolsero nel Cile socialista di Allende poco prima del colpo di Stato di Pinochet, appoggiato anch'esso dal governo di Washington Del 1975 è L'affare della Sezione Speciale, incentrato sui processi del governo di Vichy.
Ha avuto anche una parentesi da attore, recitando in tre film del regista John Landis, accanto ad altri registi famosi, tutti impegnati in brevi cameo: