Sorti en août 1994 aux Etats-Unis et en septembre 1994 en France, Tueurs nés a déclenché de vives polémiques, souvent accusé d'utiliser l'ultra-violence qu'il entend dénoncer à des fins spectaculaire et mercantile.
La mouture de base de Tueurs nés est l'oeuvre de Quentin Tarantino. Le futur réalisateur de Pulp Fiction a cependant pris ses distances avec le film d' Oliver Stone, estimant que les nombreuses réécritures du script avaient changé sa nature initiale.
Les personnages de Mickey et Mallory sont inspirés d'un véritable couple de tueurs, Charles Starkweather et Caril Fugate, qui sévirent aux Etats-Unis en 1958, responsables de 11 meutres dans 5 états des Etats-Unis.
Plus de 150 plans de Tueurs nés ont dû être coupés ou retravaillés afin d'obtenir une classification "R" ("Restricted", interdit aux moins de 17 ans non accompagnés) au film pour sa carrière américaine et éviter la mention "NC-17" (strictement interdit aux moins de 17 ans), qui équivaut à la mort commerciale de l'oeuvre. En France, le film d' Oliver Stone est interdit aux moins de 16 ans lors de sa sortie en salles.
Pas moins de 11 mois ont été nécessaires pour aboutir au montage définitif de Tueurs nés. Selon les estimations, le film se compose de 2500 à 3000 plans, alors qu'un long métrage n'en contient généralement que 600 à 700. Parmi les "victimes" de la table de montage : Ashley Judd, tuée par Mickey et Mallory dans l'un de ses premiers rôles au cinéma et seulement présente dans la "director's cut" du film sortie en DVD, d'une durée de 122 minutes contre 118 pour la version exploitée en salles.
Dix-huit formats différents ont été utilisés pendant le tournage de Tueurs nés, du 35 mm à la vidéo en passant par le 16 mm et le 8 mm. Baignant dans une ambiance psychédélique, le film passe également subitement d'un genre à un autre, allant du drame à une quasi-parodie de soap opéra et n'hésitant pas à inclure des morceaux animés.
Afin de rester dans l'ambiance hystérique du film, de la musique agressive était diffusée sur les plateaux de Tueurs nés. Selon d'autres témoignages, des coups de feux étaient également tirés en l'air pour mieux maintenir les acteurs dans une tension permanente.
Autre trace du passage de Quentin Tarantino dans le script de Tueurs nés, le nom du personnage de Tom Sizemore, Jack Scagnetti, ressemble étrangement à celui de l'officier de probation de Vic Vega (Michael Madsen) dans Reservoir dogs, nommé Seymour Scagnetti. Parmi les victimes de Mickey et Mallory se trouve par ailleurs un policier nommé Gerald Nash. Celui-ci aurait-il un lien de parenté avec l'infortuné agent de police Marvin Nash torturé lors d'une scène mémorable de Reservoir dogs ?
L'acteur Michael Madsen avait un temps été envisagé pour incarner Mickey. Il aurait refusé sur les conseils de Quentin Tarantino, qui venait de le diriger dans son Reservoir dogs.
Malgré, ou à cause de, son contenu polémique, Tueurs nés a été récompensé à de nombreuses reprises, notamment au Festival de Venise 1994 où le film a cumulé le Prix spécial du jury et le Prix de la meilleure actrice (pour Juliette Lewis). Oliver Stone a également été nommé au Golden Globe du Meilleur réalisateur en 1995.