Los Angeles Lakers

Po sezóne 95/96 sa O'Neal stal voľným hráčom. V lete 1996 bol pozvaný do národného mužstva, reprezentovať USA na olympiáde v Atlante, kde získal zlatú medailu. Kým sa s národným mužstvom pripravoval na Olympiádu, Orlando Sentinel zverejnili prieskum, v ktorom sa fanúšikov pýtali, či by Orlando mali vyhodiť Hilla za cenu návratu Shaqa. 82% ľudí odpovedalo "nie". Ďalšou otázkou v ankete bola, či je Shaquille hodný kontraktu na 115 miliónov dolárov a 91.3% ľudí taktiež odpovedalo zápornou odpoveďou. O'Neal sa taktiež dozvedel, že Hardaway sa označil za vodcu Magic a nechce, aby Shaq zárabal viac ako on. Počas prvého dňa Olympiády bol ohlásený prestup do LA Lakers na 121 miliónov dolárov. Vyhlásenia, že do Los Angeles prestúpil kvôli peniazom odmietal. "Som unavený z rokovaní o peniazoch. Všade len peniaze, peniaze, peniaze," povedal O'Neal po podpise. "Ja chcem len niekde hrať, piť Pepsi a obliekať Reebok," dodal s odkazom na niektoré produkty, ktoré propagoval.

V sezóne 96/97 Lakers vyhrali 56 hier a O'Neal v priemere zaznamenal 26.2 bodov a 12.5 doskokov, ale pre zranenie znovu chýbal viac ako 30 hier. V druhom kole playoff Lakers narazili na Utah Jazz, s ktorým prehrali v piatich zápasoch. Dňa 17.decembra sa dostal do konfliktu s hviezdou Chicaga Bulls, Denisom Rodmanom, do ktorého strčil a len Rodmanovi spoluhráči, Jordan a Pippen, zabránili ďalšej šarvátke.
Nasledujúcu sezónu O'Neal priemeroval so štatistikami 28.3 bodov a 11.4 doskokov a s percentuálnou úspešnosťou 58.4% viedol NBA. Lakers zakončili sezónu s bilanciou 61-21, druhí v západnej konferencii a potom, čo vyradili Portland a Seattle SuperSonics, opäť narazili na Utah Jazz, ktorý ich tentokrát vyradil v štvorzápasovej sérii.

Od tandemu O'Neal-Kobe Bryant sa očakávania v Lakers zvýšili. Avšak personálne zmeny boli počas sezóny 1998/99 príčinou nestabilného obdobia. Dlhoročný point guard Nick Van Exel bol vymenený do Denveru Nuggets, Eddie Jones a center Elden Campbell odišli a namiesto nich prišiel Glen Rice (na O'Nealovu žiadosť získať strelca). Tréner Del Harris bol prepustený a na jeho post nastúpil Kurt Rambis. Lakers vo výlukou skrátenej sezóne skončili s bilanciou 31-19 a v druhom kole boli vyradený neskroším šampiónom zo San Antonia.

Majstrovské obdobie

V roku 1999 prišiel do Los Angeles na post hlavného trénera Phil Jackson. Ihneď motivoval O'Neala, keď mu hovorieval, že MVP trofej bude raz pomenovaná po ňom. Použitie Jacksonovho ofenzivneho trojuholníka, O'Neala a Bryanta si užilo obrovského úspechu a doviedol Lakers k trom, po sebe idúcim titulom (2000, 2001 s 2002). Shaquille bol navyše vo všetkých troch finále menovaný za MVP a mal najvyšší priemer skóre v histórii finále NBA.

O'Neal bol v sezóne 1999/2000 zvolený aj za MVP sezóny. Iba jeden hlas ho delil od ďalšieho míľnika a to aby sa stal po prvý krát jednomyseľne zvoleným MVP. Fred Hickman si však zvolil Allena Iversona. O'Neal viedol rebríček v skórovaní, v doskakovaní skončil na druhom mieste a na treťom v blokovaní. Shaquille sa v roku 2000 ocitol aj v prvom All-Defensive tíme.

V lete 2001 bol vyzvaný k priateľskému wrestlingovému zápasu budúcim hráčom NBA Glenom Davisom. 160 kilogramov vážiaci O'Neal v tomto súboji prehral a mesiac pred kempom sezóny 01/02 musel podstúpiť operáciu zdeformovaného prstu na nohe. Na sezónu bol pripravený, ale prst ho často bolel. V januári 2002 sa zapojil do bitky s hráčmi Chicago Bulls a potom čo udrel Brada Millera bol suspendovaný na tri zápasy a pokutovaný na 15 000 dolárov. Sezónu zakončil s priemerom 27.2 bodov a 10.7 doskokov na zápas, čo boli vynikajúce štatistiky, avšak pod jeho kariérnym priemerom.

Pred finále konferencie sa O'Neal Nechal počuť že "Je len jeden spôsob ako nás poraziť. Začína na C a končí na T." Myslel tým slovo "cheat", čo v angličtine znamená "podvádzať". Mal pravdu a LA Lakers titul obhájili.

Po sezóne povedal, že už nechce ďalšiu sezónu kvôli prstu krívať, pociťovať prakticky konštantnú bolesť a tak chirurgiu skombinoval s liekmi.

Na začiatku sezóny 2002/03 sa zotavoval z operácie a vynechal prvých 12 zápasov. To že čakal až do poslednej chvíle, kým sa nechá operovať vysvetlil slovami "zranil som sa v pracovnej dobe, tak sa v pracovnej dobe budem aj liečiť." Lakers začali sezónu s bilanciou 11-19 a nedosiahli ani na finále.
Hneď po sezóne chceli zlepšiť súpisku a O'Neal pomohol presvedčiť Karla Maloneho a Garyho Paytona aby podpísali s Lakers.

Na začiatku sezóny 2003/04 Shaq chcel predĺženie zmluvy na tri roky a 30 miliónov, avšak Lakers dúfali, že kvôli jeho veku, problémom so zraneniami a fyzickej kondícii bude chcieť menej. Navyše rástlo aj napätie medzi ním a Kobem, ktorý v rozhovore pre ESPN Shaqua kritizoval pre jeho zlú formu, že je to zlý vodca a ten plat si nezaslúži.

Vo finále NBA v roku 2004 prehrali s Pistons. Po nezhode s vedením a po tom čo sa vyjadril, že klub urobil všetko pre uspokojenie Bryanta, požadoval odchod. Lakers ho chceli vymeniť do Mavericks za Dirka Nowitzkeho, ale Cuban to odmietol. Záujem prejavili Heat a nakoniec sa tieto dva kluby aj dohodli.