Nel 1985 si laurea in architettura a Firenze con una tesi su Victor Hugo e la cultura del restauro moderno. Il suo romanzo d'esordio è del 1988, il grottesco e visionario Per dove parte questo treno allegro mentre con Gli sfiorati (1990) Veronesi si afferma come scrittore capace e brillante.
Nel 1995 esce Venite, venite B52, romanzo che lo avvicina al mondo letterario americano, Thomas Pynchon su tutti. Nel 2000 pubblica La forza del passato, vincitore del Premio Campiello e del Premio Viareggio e tradotto in 15 lingue. Da quel romanzo è tratto l'omonimo film di Piergiorgio Gay. Nel 2001 pubblica il libro per ragazzi Ring City che vince il Premio Fregene.
Veronesi è anche autore di quattro libri non fiction: le raccolte di interviste Cronache italiane (1992), Live (1996), Occhio per occhio (1992), inchiesta sulla pena di morte nel mondo (ristampato nel 2006 dall'editore Bompiani) e Superalbo (2002), libro che contiene i suoi articoli giornalistici.
Nel 1997 e fino ai primi mesi del 1998 collabora con Rai Tre ed è autore e conduttore del programma televisivo "Magazzini Einstein - cibo per la mente", regia di Arturo Minozzi.
Nel 2003 pubblica la riduzione teatrale di No Man's Land e nel 2006 vince il Premio Strega grazie al romanzo Caos calmo, uscito l'anno precedente. Il 9 maggio 2007 esce, presso Bompiani, il romanzo Brucia Troia.
Collabora con numerosi quotidiani e riviste letterarie; insieme a Domenico Procacci ha fondato la casa editrice Fandango Libri. Risiede a Prato con i suoi tre figli. Ed è tra i fondatori della radio web Radiogas. Nel 2008 vince a Parigi il premio Femina straniero con Caos calmo.

Ha pubblicato su Colla: Morto per qualcosa.