L'idée de Gangs of New York remonte à ... 1970, lorsque Martin Scorsese découvrit le roman homonyme de Herbert J. Asbury lors d'un week-end passé chez des amis. Le réalisateur en demanda presque immédiatement l'adaptation cinématographique à son ami scénariste Jay Cocks. En 1977, tous deux annoncent le lancement du projet à la presse. Mais des problèmes essentiellement budgétaires les obligent à repousser sans cesse le tournage, jusqu'à la fin des années 90 lorsque Miramax accepte de produire le film. Les prises de vue démarrent en septembre 2000.
Tourné entre septembre 2000 et avril 2001, Gangs of New York a vu sa date de sortie repoussée plusieurs fois. D'abord prévu pour la fin décembre 2001, le film a été décalé en raison des attentats du 11 septembre 2001. Annoncé tour à tour pour le début de l'année 2002, pour l'ouverture du Festival de Cannes 2002 (où 20 minutes du film seront tout de même finalement présenté en grande pompe) et pour le mois de juillet 2002, Gangs of New York sort finalement le 20 décembre 2002 aux Etats-Unis. Des rumeurs de désaccord entre Martin Scorsese et sa production au sujet de la durée du film ont par ailleurs foisonné dans la presse spécialisée au fur et à mesure des décalages de la date de sortie.
L'intrigue de Gangs of New York mélange des événements réels à d'autres purement inventés. Ainsi les terribles émeutes qui secouent New York à la fin du film et leur répression se sont déroulées en 1863 et sont connues sous le nom de Draft Riots. Le personnage de Bill le Boucher est lui aussi inspiré d'un personnage ayant réellement existé. Boucher devenu boxeur professionnel, Bill Poole, connu partout sous le surnom de Bill le Boucher, est cependant mort en 1855 et n'a donc pas pu assister aux Drafts riots comme le personnage de Daniel Day-Lewis dans le film. Purement imaginée, l'histoire de la vengeance d'Amsterdam est un grand classique du drame, alors que son héros est inspiré des paroles d'une chanson de Bruce Springsteen : "attendre un sauveur qui se dresse, venu de la rue".
La scène d'ouverture de Gangs of New York qui voit un homme se raser en gros plan se veut un hommage à l'un des premiers courts métrages de Martin Scorsese, Le Grand rasage, entièrement centré sur le rasage de son héros.
Gangs of New York marque les retrouvailles de Martin Scorsese avec Daniel Day-Lewis, qu'il avait déjà dirigé en 1993 dans Le Temps de l'innocence.
Le rôle de Bill le Boucher, l'un des héros de Gangs of New York, avait un temps été dévolu à Robert De Niro, ami de Martin Scorsese qui l'a dirigé à huit reprises. Le nom de Willem Dafoe avait également circulé, avant que le metteur en scène ne convainque Daniel Day-Lewis de sortir de sa semi-retraite en Italie.
Décidé dès le lancement du projet à reconstruire le vieux New York plutôt que d'avoir recours aux effets spéciaux optiques, Martin Scorsese a fait appel à son chef décorateur Dante Ferretti (cinq collaborations) pour recréer les rues de la ville à Cinecitta, sur un terrain de 6 hectares. Outre le quartier de Five Points et les quais du port, les équipes de Gangs of New York ont également reconstruit une partie du Sud de Broadway où vivait alors la classe supérieure, différentes résidences privées et les environs de la Catholic Church, ancêtre de la Cathédrale St Patrick près de laquelle Martin Scorsese a grandi. L'intérieur de l'Old Brewery, le repaire grouillant de la communauté irlandaise de Five points a, lui, été inspiré d'une illustration de "l'Encyclopédie" de Diderot, aucune photo ou illustration n'ayant été découvertes. Des maquettes du quartier en trois dimensions ont été créées principalement pour préparer les vastes mouvements de caméra nécessaires à la mise en scène. Enfin, le réalisateur et ses collaborateurs avaient récupéré quelques 850.000 objets de l'époque découverts lors des travaux d'agrandissement d'un parking de la ville. Rassemblé au building 6 du World Trade Center, ceux-ci ont cependant presque totalement disparus lors des attaques du 11 septembre 2001. Seul 18 objets ont été retrouvés.
Dans l'impossibilité de tourner son film à New York même en raison des trop importants changements architecturaux de la ville, Martin Scorsese s'est tourné vers les plateaux de Cinecitta situés à Rome, qui possédait un terrain suffisamment grand pour récréer le quartier de Five points en taille réelle et un bassin imposant utilisé pour les scènes du port.
Centre névralgique de l'action de Gangs of New York, le quartier de Five Points se situe au nord-est de l'hôtel de ville actuel, essentiellement sur le site de Federal Court House.
Pour son ambitieux projet, Martin Scorsese s'est entouré de quelques-uns de ses plus fidèles collaborateurs. Ainsi Gangs of New York marque-t-il la sixième collaboration de Martin Scorsese avec le directeur de la photographie Michael Ballhaus (après After Hours, La Couleur de l'argent, La Derniere Tentation du Christ, Les Affranchis et Le Temps de l'innocence), la cinquième avec le chef décorateur Dante Ferretti, la dix-neuvième avec la monteuse Thelma Schoonmaker, la deuxième avec le scénariste et ami de longue date Jay Cocks (après Le Temps de l'innocence) et la deuxième avec le compositeur Howard Shore (après After hours). Le film est par contre une première pour la chef costumière Sandy Powell.
Pour préparer leur combat final, Leonardo DiCaprio et Daniel Day-Lewis se sont entraînés des mois durant avec Martin Scorsese et George Aguillar, coordinateur des cascades. D'une durée de 11 mois, le programme de Leonardo Di Caprio comportait notamment du lever de poids, du lancer de couteaux et différentes techniques de combats de l'époque.
Afin de restituer l'accent des habitants de New York du milieu du 19e et à leur argot spécifique (les mots "crèches" et "fourguer" sont nés à Manhattan), un coach spécialement dédié aux dialogues a été engagé. Surnommé "police de prononciation d'époque", Tim Monich a ainsi travaillé sur les accents de plus de 100 personnes, dont quasiment aucun ne s'exprime avec sa prononciation naturelle. N'ayant aucun d'enregistrement de l'époque à analyser, Tim Monich s'est basé sur des pamphlets humoristiques, de poèmes, des ballades et des extraits de la presse pour restituer le bon vocabulaire. Ainsi, Leonardo DiCaprio avait-il tendance à gommer l'expression "okay" qu'il prononce machinalement avant que Tim Monich ne lui précise que ce mot était déjà utilisé dans le langage courant de l'époque.
Vaste fresque historique, Gangs of New York possède une distribution des plus imposantes, avec 100 rôles parlant et plus de 22 000 figurations diverses. Italiens pour la plupart, les figurants se sont souvent fait teindre les cheveux en blond pour ressembler à des irlandais. Un autre groupe important de figurants à été recruté dans les bases de l'armée américaine situées près de Rome, où se tournait le film.
Les histoires des gangs qui sévissaient dans les New York des années 1860 ont bercé l'enfance de Martin Scorsese de l'aveu même du metteur en scène, qui habitait dans le quartier de Little Italy, non loin de la Cathédrale de St Patrick qui abrite le premier cimetière catholique de New York.
Pour organiser les prises de vue des combats qui impliquaient des centaines de figurants, l'équipe de Gangs of New York a mis en place une véritable organisation militaire. "Nous avons envisagé le tournage comme si nous étions dans l'armée", raconte George Aguillar, coordinateur des cascades. "Nous avons divisé nos centaines d'acteurs en groupes plus petits, en peloton, en désignant un responsable pour chaque. Les chefs de peloton étaient chargés de transmettre les directions de Martin à leur groupe"