A nagy lehetőség, hogy a színházi munkáról a filmszínészetre váltson, csupán két évvel színházi debütálása után jelentkezett. Miután Leonardo DiCaprio lemondta a főszerepet a Legbelső félelem című bűnügyi thrillerben, a film produkciós vezetői meghallgatást hirdettek meg a szerepre. Edward Nortont 2100 esélyes közül választották ki. Mivel a ministráns fiú karaktere Kentucky keleti részéről származott, Edward Norton magabiztos és hiteles akcentussal tudatta a meghallgatáson részt vevő rendezőkkel, hogy ő bizony éppen onnan származik. A legenda úgy tartja, hogy Edward számtalanszor végignézte A szénbányász lánya című filmet, hogy hibátlanul megtanulhassa az illető akcentust. Átütő erejű alakítása már a szövegolvasási próbákon nagy hatással volt az egész stábra, és már a film megjelenése előtt sztárként kezelték. Az 1996-ban bemutatott Legbelső félelem-ben Edward valóban tökéleteset alakított, és kritikusok szerint megmentette az egyébként középszerű filmet. Játékát Golden Globe-bal és Oscar-jelöléssel jutalmazták a legjobb férfi mellékszereplői kategóriában.
Ezek után özönlöttek az ajánlatok: még ugyanabban az évben egy Woody Allen-filmben, a Varázsige: I Love You című romantikus, zenés vígjátékban játszott, amelyben saját hangján énekelt is, véglegesen meggyőzve ezzel a filmkritikusokat sokoldalúságáról. 1996-ban újra egy dráma következett, a Larry Flynt, a provokátor, amelyben Edward a védőügyvédet alakította.
Bár Edward Norton karrierje ekkor már a lehető legjobb úton haladt, alakítása az 1998-as Amerikai história X-ben véglegesítette státusát Hollywoodban: generációja legnagyszerűbb színészének tartották. Golden Satellite-díjat kapott, és megkapta második Oscar-jelölését.
A kilencvenes évek folyamán és 2000-es évek elején olyan filmekben szerepelt, mint a Pókerarcok (Rounders), Harcosok klubja (Brad Pitt és Helena Bonham Carter partnereként), A Szajré (Robert De Niróval), vagy a Spike Lee rendezte Az utolsó éjjel. Norton rendezőként 2000-ben mutatkozott be az Ég velünk! című romantikus komédiában, amelynek szereplője is volt.
Az utolsó éjjel (The 25th Hour) című filmben Norton egy drogdílert játszik, aki utolsó szabad napját tölti a szeptember 11. utáni New Yorkban. Az ismert rendező, Spike Lee egy olyan, nehézéletű embert mutat be, akit rengeteg kétely gyötör azzal kapcsolatban, hogyan is juthatott idáig, miközben az utolsó utáni pillanatban is küzd, hogy visszanyerje egykori énjét. Nemcsak neki, hanem környezetének is legalább olyan nehéz szembesülni a ténnyel, hogy a barátjuk 24 órán belül a börtönben köt ki. Nem tudják, mit is mondjanak neki, hogyan viselkedjenek vele az utolsó órákban, beszéljenek-e az egészről, vagy inkább csak rúgjanak be, és bulizzanak egyet...
Ez a hosszú lista rivalizál egy ugyanilyen hosszú, a visszautasított nagy szerepek listájával: játszhatott volna a Ryan közlegény megmentésé-ben, a Hart háborújá-ban, Az őrület határán-ban, és az Amerikai psycho-ban, amelyeket részben szakmai nézeteltérések és részben családi tragédiák miatt utasított el. Nagyapja 1996-ban meghalt, édesanyját pedig egy évvel később veszítette el. 2002-ben ő játszotta az egyik főszerepet a várva várt Hannibal-film folytatásában, a Vörös Sárkány-ban, 2003-ban pedig feleségével, Salma Hayekkel játszott együtt a Frida című életrajzi filmben.