VERHAALLIJN: Op 6 februari 1846 vindt er op Paradise Square in de Five Points een territoriale strijd plaats tussen de in de Verenigde Staten geboren bendeleden van The Natives onder leiding van Bill "The Butcher" (Daniel Day-Lewis), en de Dead Rabbits, een bende bestaande uit Iers-katholieke immigranten onder leiding van Priester Vallon (Liam Neeson ). De jonge Amsterdam Vallon ziet hoe zijn vader tijdens het gevecht wordt neergestoken door Bill The Butcher. Amsterdam grijpt het mes waarmee zijn vader gedood is en slaat op de vlucht. Hij begraaft de medaille van Sint Michael die hij eerder kreeg van zijn vader samen met het mes. Hij belandt in het opvoedingsgesticht Hellgate op Blackwell's Island. Na het gevecht worden de Dead Rabbits verboden. Eind 1862 keert de volwassen Amsterdam Vallon (Leonardo DiCaprio) terug naar de Five Points, waar hij zijn jeugdvriend Johnny Sirocco (Henry Thomas) terug ontmoet. Tijdens hun gesprek treffen ze Jenny Everdeane (Cameron Diaz) een dievegge en zakkenrolster. Johnny voelt zich aangetrokken tot haar. Als ze even later de medaille van Amsterdam steelt, zet Amsterdam de achtervolging in en betrapt haar op heterdaad. Ook bij hem ontstaan gevoelens voor de jonge vrouw, maar ontdekt dan dat ze goed bevriend is met Bill The Butcher. Johnny stelt Amsterdam voor aan Bill zonder zijn afkomst te vermelden. Amsterdam stelt met verbazing vast dat gewezen leden van de Dead Rabbits nu voor Bill werken. Onder andere Jack Mulraney (John C. Reilly), die nu een corrupte politieagent is, en de racistische McGloin(Gary Lewis) zijn overgelopen. Amsterdam zelf wordt ook een vertrouweling van Bill en ontdekt dat de dood van zijn vader jaarlijks gevierd wordt met een ceremonie. Na zich in de bende te hebben ingewerkt raakt Amsterdam ook betrokken bij Tammany Hall en het corrupte politieke rijk van "Boss" Tweed, die gemanipuleerd wordt door Bill. Tijdens een theatervoorstelling probeert een man uit het publiek Bill dood te schieten. Amsterdam waarschuwt Bill, waardoor die aan de dood ontsnapt. Na het incident trekken ze zich terug in een hoerenkast, waar Bill zijn schotwonde laat verzorgen door Jenny. Vervolgens maken Amsterdam en Jenny ruzie, waarna de twee samen de liefde bedrijven. Die nacht wordt Amsterdam wakker en ontdekt hij dat Bill, met een Amerikaanse vlag over zijn schouder, naast zijn bed zit te mijmert over hoe Priester Vallon zijn laatste eervolle tegenstander was en dat Vallon hem ooit verslagen had. Vallon besloot toen om hem niet te doden zodat hij de rest van zijn leven in schaamte zou moeten slijten. Daarnaast noemt hij Amsterdam de zoon die hij nooit gehad heeft. Johnny kan de relatie tussen Amsterdam en Jenny niet verwerken. In een jaloerse bui besluit hij om Amsterdam te verraden. Hij rent naar Bill om de ware identiteit van zijn jeugdvriend te onthullen. Tijdens de jaarlijkse ceremonie om Priester Vallons dood te vieren, kruipt Bill op het podium en daagt hij Jenny uit om richtpunt te worden van een act waarin met messen wordt geworpen. Tijdens de act verwondt hij Jenny, waardoor hij Amsterdam verleidt tot het plegen van een moordaanslag. Wanneer Amsterdam hem met een mes probeert aan te vallen, grijpt Bill in en verwondt hij Amsterdam door een mes in zijn buik te werpen. Nadien verbrandt hij het gelaat van Amsterdam, zodat die voortaan met een afzichtelijk gelaat door het leven moet. Terwijl hij herstelt van zijn verwondingen, stelt Jenny aan hem voor om New York te verlaten voor Californië. Tijdens zijn revalidatie krijgt Amsterdam bezoek van Walter "Monk" McGinn, een huurling die in het verleden aan de zijde van zijn vader vocht. Monk weet hem te overtuigen om de moed niet op te geven. Na zijn revalidatie plaatst Amsterdam een dood konijn op Paradise Square. Bill begrijpt het dreigement en gelast Jack Mulraney om Amsterdam op te sporen. Amsterdam overmeestert de corrupte agent, waarna diens lichaam op Paradise Square wordt opgehangen. Als wedervergelding wordt Amsterdams jeugdvriend Johnny op hetzelfde plein opgehangen aan een hek. Amsterdam verlost hem uit zijn lijden en maakt hem af. "Boss" Tweed is niet tevreden met Bills manier van werken en benadert Amsterdam met een plan om samen de macht te grijpen. Amsterdam zorgt ervoor dat de Ierse gemeenschap achter Tweed staat en in ruil wordt: "Monk" McGinn verkozen als sheriff. Zowel Amsterdam als Bill pleegt verkiezingsfraude en gebruiken geweld om de uitslag te manipuleren. Monk wint met overtuiging de verkiezing, waarna hij door Bill in koelen bloede vermoord wordt. Tijdens Monks uitvaartplechtigheid daagt Amsterdam zijn rivaal Bill uit voor een traditioneel gevecht. Jenny vreest dat Amsterdam de strijd niet zal overleven en besluit naar Californië te reizen. Ondertussen breken de dienstplichtrellen in New York uit. Zowel de rijken uit de hogere klasse van de samenleving als Afrikaanse Amerikanen worden door de relschoppers aangevallen. Soldaten die tot de Unie van Noordelijke Staten behoren, worden ingeschakeld om de relschoppers in New York tegen te houden. Tijdens het gevecht tussen de bendes van Bill en Amsterdam wordt de stad getroffen door kanonskogels van de schepen uit de haven. Heel wat bendeleden komen om het leven en de straten raken gevuld met rook en stof. Wanneer de rook verdwijnt, ontdekt Bill dat hij geraakt is door een stuk shrapnel en zegt: "Godzijdank, ik sterf als een ware Amerikaan." Vervolgens steekt Amsterdam hem dood en houden de twee elkaars hand vast. Bill wordt in Brooklyn begraven naast het graf van Priester Vallon, dat door Amsterdam en Jenny bezocht wordt alvorens ze samen vertrekken. Amsterdam vertelt vervolgens dat New York zal herbouwd worden, maar dat zij niet langer herinnerd zullen worden, alsof ze er nooit waren. Op de achtergrond verandert de skyline van de stad in het moderne New York. De Brooklyn Bridge, de Empire State Building en het World Trade Center verschijnen in beeld, terwijl op de voorgrond de graven van Bill en Vallon worden overwoekerd. D.D. voor Libertina Movie.