Advocat, ingressà al cos de policia i els anys 1952-58 treballà en una comissaria de Rio de Janeiro. El 1963 debutà amb el recull de narracions Os prisioneiros. Autor d’una trentena de títols de gènere negre, entre novel·les i narracions, la violència i l’erotisme extremament gràfics del seu llenguatge i les seves imatges el situaren al centre de controvèrsies, que arribaren fins a la prohibició d’alguns dels seus llibres.
Entre les seves obres més difoses, dins i fora del seu país, hi ha les narracions Lúcia McCartney (1969), Feliz Ano Novo (1975), O cobrador (1979) i Carne Crua (2018), i les novel·les O Caso Morel (1973), Bufo & Spallanzani (1986), Agosto (1990), considerada la seva millor obra, la trama de la qual gira entorn de l’assassinat del president Getúlio Vargas, i O seminarista (2009).
El personatge de l’advocat Mandrake, creació notòria pel cinisme i la falta d’escrúpols, obtingué una gran popularitat a través de la sèrie de televisió homònima emesa des del 2005, basada en els relats de Fonseca.
Rebé els premis Camões (2003), el més important en llengua portuguesa, el Juan Rulfo (2003), el Konex Mercosur (2004), el Manuel Rojas (2012) i el Machado de Assis (2015), entre d’altres.