Michael Mann, maestro nel creare inediti scenari urbani, da sempre ama affiancare alle sue storie di sbirri e criminali colonne sonore originali e all'avanguardia. Dai Tangerine Dream per "Strade Violente" a Moby per "Heat" sino a Lisa Gerrard per "Insider" e "Alì", le colonne sonore dei film di Mann si sono sempre segnalate per scelte non scontate e accattivanti. E "Nemico Pubblico" non fa eccezione. Certo, la cornice d'epoca costringe il regista a scelte "obbligate": l'inconfondibile voce di Billie Holiday è la protagonista di questa soundtrack, comparendo in ben tre brani (il più bello è "The Man I Love"), ma a restare nella memoria è soprattutto l'intenso score di Elliot Goldenthal (premio Oscar per "Frida", ma collaboratore di vecchia data del regista), che sottolinea con toni drammatici e operistici la fatalità dell'amore tra il bandito John Dillinger e la stupenda Billie Frechette (vedi episodi come "Billie's Arrest" o "JD Dies"), per abbandonarsi anche a toni più intimi e romantici ("Love In The Dunes").
Il vero main theme della pellicola è però affidato a Otis Taylor e alla sua "Ten Million Slaves", un trascinante blues dove il banjo è affiancato alla ruvidezza di una chitarra elettrica (nel film il brano si può ascoltare in due delle sequenze più importanti). Essenziale dal punto di vista narrativo pure "Bye Bye Blackbird", qui interpretata alla perfezione da Diana Krall, che nella pellicola può essere ascoltata a suggello della dichiarazione d'amore di Dillinger nei confronti di Billie. In dirittura d'arrivo il funereo, essenziale, blues di Blind Willie Johnson, "Dark Was The Night, Cold Was The Ground". Ancora una volta Michael Mann ha fatto centro.