A magyar felmenőkkel is rendelkező Paul Leonard Newman az Ohio állambeli Cleveland külvárosában jött a világra. Apja azt szerette volna, ha ő viszi tovább sportszerboltját, de Pault inkább a sportkarrier és a repülés vonzotta. A légierőtől azonban színvaksága miatt eltanácsolták, sportpályafutásának baleset vetett véget. Az egyetemen közgazdaságtant és irodalmat tanult, majd apja halála után átvette az üzletet, de a színház vonzásának nem tudott ellenállni. Családja neheztelését kiváltva a Yale Egyetemen kezdett színi tanulmányokba, majd New Yorkban Lee Strasberg legendás stúdiójába iratkozott be, közben kisebb szerepet játszott egy tévésorozatban.
Először 1955-ben egy kosztümös darabban állt a kamerák elé, egy évvel később a Valaki odafönt szeret engem című filmben a legendás bokszoló, Rocky Graziano megszemélyesítéséért megkapta az év felfedezettjének járó Golden Globe-díjat. 1958 szakmai és magánéletében is fontos állomás lett: a Hosszú, forró nyár című film forgatásán ismerkedett meg második feleségével, Joanne Woodwarddal, s alakításáért a cannes-i filmfesztiválon díjazták, a Macska a forró bádogtetőn című filmért pedig Elizabeth Taylor partnereként Oscar-díjra jelölték.
A hatvanas években forgatta leghíresebb filmjeit, köztük Az ifjúság édes madara, A hallgatag ember, a Bilincs és mosoly, valamint a Butch Cassidy és a Sundance kölyök címűt. Utóbbi westernben először játszott Robert Redforddal, akivel 1973-ban legendás párost alkottak az Oscar-díjas gengszterkomédiában, A nagy balhéban is.
1968-ban debütált rendezőként, a Rachel, Rachel című dráma Oscar-jelölést kapott, őt pedig Golden Globe-díjjal tüntették ki.
Newman több műfajban is kipróbálta magát: játszott a nagy kasszasikert hozó Pokoli toronyban, a Buffalo Bill és az indiánok című westernben, a Kvintett című futurisztikus drámában, dolgozott Sydney Pollackkal (A szenzáció áldozata) és Sidney Lumet-val (Az ítélet). 1986-ban Martin Scorsese A pénz színe című alkotásában nyújtott alakításáért (hatodik színészi jelölése után) átvehette a legjobb színésznek járó aranyszobrot. Bár nyugdíjas korba érve számos felkérést visszautasított, a Senki bolondja című vígjátékért 1994-ben újra Oscarra jelölték a legjobb színészek közt. Élete utolsó évtizedében látható volt az Üzenet a palackban című szerelmi románcban, a Pénzt vagy életet című vígjátékban.
2002-ben csaknem negyven év után, Thornton Wilder A mi kis városunk című darabjában ügyelőként lépett ismét színpadra, alakításáért Emmy- és Tony-díjra is jelölték, utóbbira – hetvennyolc évesen – életében először. 2008-ban színházi rendezői debütálásaként Steinbeck Egerek és emberek című darabját állította volna színpadra, de betegsége miatt erre már nem kerülhetett sor. Tüdőrákja egyre súlyosbodott, és 2008. szeptember 26-án otthonában a connecticuti Westportban meghalt, emlékére egy héttel később a Broadway valamennyi színháza elsötétült egy percre.
A legendás színész Frank Sinatra mellett egyedüliként kapott színészi Oscar-díjat, Jean Hersholt humanitárius díjat és különleges/életmű-Oscart. Alapítványa hátrányos helyzetű, valamint rákbeteg gyerekek, drog- és alkoholfüggő fiatalok gyógyítását támogatta, ebben szerepet játszhatott, hogy első házasságából született, egyetlen fia 1978-ban kábítószer-túladagolásban halt meg. Üzletemberként is sikeres volt, élelmiszeripari vállalkozása bevételének egy részét ugyancsak humanitárius célokra fordította.
Ő maga filmjei közül a Jégtörők című hokis komédiát tartotta kedvencének, amelyben egy veterán edzőt alakított. A színész hangját a Verdák 3 című animációs filmben (2017), az első részt idézve halála után kilenc évvel ismét hallani lehetett.
Érdekesség, hogy 2013-ban Newman és felesége, Joanne Woodward egy fél évszázaddal korábban készült filmes csókja került a cannes-i filmfesztivál plakátjára. A házaspár számos bútorát, műalkotását, ékszerét a becsült ár csaknem háromszorosáért, több mint négymillió dollárért árverezték el 2023-ban.
A liberális nézeteit soha nem titkoló Newman, aki BAFTA-, Emmy- és Ezüst Medve-díjjal is büszkélkedhetett, többször felemelte szavát a feketék egyenjogúságáért, a nukleáris leszerelésért, nem csoda, hogy a Watergate-botrány idején előkelő helyen szerepelt a Nixon elnök által nemkívánatosnak tekintett személyek listáján.
Maga azt tartotta, Hollywood csak szerencsejáték: ahhoz, hogy ki nyer, a tehetségnek kevés köze van, ő is pusztán jókor volt jó helyen. Hat filmje került be a Kongresszusi Könyvtár Nemzeti Filmregiszterébe. Csillaga 1994 óta díszíti a hollywoodi Hírességek sétányát. Emlékiratait (Extraordinary Life of an Ordinary Man) 2022-ben adták ki.