Nový kouč, první All-Star a Malone jako ofenzivní lídr (87-96)

Do sezóny 1987-88 vstoupili Jazz s Malonem jakožto lídrem ofenzívy, když celému útoku velel generál John Stockton. Robustní PF získalo v roce 1988 první pozvánku do prestižní All-Star Game, když si v sezóně připisovalo průměrně 27,1 bodů na zápas. Byl to jeho první All-Star zápas ze 14, kterých se Malone zúčastnil (všechny po sobě s výjimkou roku 1999). Připsal si zde nejvíce bodů z celého týmu Západu - 22. V této sezóně se Malone "probojoval" také do první pětky ligy, která se tradičně vyhlašovala po ukončení základní části. Jazz v tomto roce obsadili třetí příčku ve Středozápadní divizi (bilance 47-35) a v prvním kole postoupili přes Portland Trail Blazers v poměru 4:0 na zápasy. V druhém kole narazili Jazz na obrovsky silné Los Angeles Lakers, které se opíralo především o famózního Magica Johnsona a dále o Jamese Worthyho a také legendárního Kareema Abdul-Jabbara. Hráči Utahu těmto hvězdám statečně vzdorovali a sérii dovedli až do sedmého utkání, zde však pozdějším šampiónům podlehli 109:98 i přes další Maloneův výborný výkon (31 bodů a 15 doskoků). V 11 utkáních play off si Malone průměrně připisoval 29,7 bodů a 11,8 doskoků a zařadil se ve své třetí sezóně mezi největší hvězdy ligy.

Maloneova kariérní ocenění:

* 14x zvolen do All-Star Game (1988-98, 2000-02)

* 2x MVP All-Star Game (1989, 1993)

* 11x První tým NBA (1988-98)

* 2x Druhý tým NBA (1988, 2000)

* 1x Třetí tým NBA (2001)

* 3x První defenzivní tým NBA (1989, 91, 92, 95, 97)

* 1x Druhý defenzivní tým NBA (1988)

* NBA All-Rookie Team (1986)

* Jeden z 50 nejlepších hráčů historie NBA

* Jeho dres č. 32 vyřazen Utahem Jazz

* Člen legendárního Dream Teamu

* Dvojnásobný olympijský vítěz (1992 Barcelona, 1996 Atlanta)

* Člen Síně slávy NBA (2010)

Po sezóně 1988 podepsal Malone desetiletou smlouvu s Utahem Jazz, která mu měla přinést 18 milionů dolarů. Layden se z pozice trenéra odsunul na prezidentské křeslo Jazz a podařilo se mu jako kouče najmout Jerryho Sloana, který byl poté Utahu jako trenér věrný dlouhých 23 let, když v roce 2011 odešel za velkých ovací do trenérského důchodu. V sezóně 1988-89 zaznamenával Malone průměrně 29,1 bodů na zápas, což bylo druhé nejvyšší číslo hned po Michaelu Jordanovi, a také 10,7 doskoků. což mu vyneslo páté místo v lize v této kategorii. Obě čísla byla do té chvíle ta nejvyšší, jakých Malone prozatím dosáhl. All-Star Game roku 1989 Malone ovládl s 29 body, 8 doskoky a 3 asistencemi a poprvé v kariéře získal ocenění nejužitečnějšího hráče zápasu All-Star. Tento rok Jazz zakončili s výbornou bilancí 51-31, ale byli hned v prvním kole smeteni ve třech utkáních (první kolo se tenkrát hrálo pouze na tři vítězství) týmem Golden State Warriors. Malone se však poprvé v kariéře dostal do první pětky celé ligy, tzv. All NBA First Teamu.

Sezóna 1989-90 pro nyní už hvězdného Malonea opět přinesla lepší statistická čísla, a to 31 bodů a 11,1 doskoků na utkání. Malone byl opět zvolen do první pětky ligy a od té chvíle už v ní nechyběl ani jednou až do roku 1999. Památným se stal 27. leden 1990, kdy "Pošťák" pří vysoké výhře 144:96 nad Milwaukee Bucks nastřílel své kariérní maximum 61 bodů. Trefil 21 z 26 střel z pole a k tomu 19 z 23 trestných hodů. To bylo nejvíce bodů vstřelených hráčem Jazz od dob, kdy se tento klub stěhoval do Utahu z New Orleans (rok 1979). Opět byl zvolen do All-Star Game, ale kvůli poranění kotníku si tentokrát tuto každoroční událost musel nechat ujít. Vrátil se však brzy do hry a to ve velkém stylu - v posledních 24 utkáních z 26 byl pokaždé nejlepším střelcem Utahu. Nejvyšší čísla v této době zaznamenal 29. března proti Warriors, když jejich konto zatížil 49 body. 12. května pak jeho řádění odnesli Lakers, kterým nastřílel 45 bodů. Klub ze Salt Lake City zakončil sezónu s bilancí 55-27, nicméně podruhé za sebou se musel před soupeřem sklonit už v prvním kole, když v pěti utkáních nestačil na Phoenix Suns. Malone v této sérii zaznamenával průměrně 25,2 bodů a 10,2 doskoků, ani to však nestačilo. Podruhé za sebou jej však mohla hřát nálepka druhého nejlepšího střelce ligy - opět za legendárním Michaelem Jordanem.

Od 19. ledna do 4. března 1991 Malone vedl bodově svůj tým v 19 utkáních po sobě. Sezóna sice pro Jazz nezačala nijak úžasně (bilance 7-8), od té chvíle však jakoby do sebe zapadla všechna kolečka a za leden a únor tým dosáhl výborné bilance 21-9. V All-Star Game roku 1991 Malone zaznamenal 16 bodů a 11 doskoků a statistiky v sezóně měl ještě o mnoho lepší - průměrně 29 bodů a 11,8 doskoků. Jazz měli v této části roku čtyři hráče, kteří průměrně dosahovali na double-double. Byli jimi mimo Malonea také John Stockton, Thurl Bailey a Jeff Malone (s Karlem však příbuzní nebyli). Jazz konečně postoupili přes první kolo (3:1 vs. Suns), ale ani v tomto roce si Malone své první konferenční finále nezahrál, když je v druhém kole vyřadil Portland. Útěchou Maloneovi mohla být alespoň další nominace do první pětky celé NBA.

Přesně jako v sezóně 1989-90, i v 1991-92 skončil Malone na druhém místě ligy mezi střelci. Průměrně si připsal 28 bodů, počtvrté za sebou se dostal do první pětky NBA a opět si zahrál i v utkání hvězd. Pro Jazz byla tato sezóna lehce průlomová - tým se totiž poprvé za Maloneovu kariéru dostal do finále konference. The Mailman si připsal další milník - během sezóny se pětkrát dostal přes hranici 40 bodů. Poprvé v kariéře se však na jeho basketbalovém životopise objevila černá kaňka. 14. prosince 1991, když Jazz přivítali Detroit Pistons, Malone doslova vyautoval hostujícího rozehrávače Isiaha Thomase, kterému uštědřil ránu loktem tak velikou, že pár desítek minut po incidentu zdobilo Thomasovu hlavu 40 stehů přes čelo až k oku. Viník za tento "výkon" vyfasoval stopku na jedno utkání a pokutu 10 000 dolarů. Avšak zpátky k finále Západní konference - podruhé za sebou byli katem Utahu Trail Blazers, kteří vyprovodili svého soka v šesti utkáních. Malone si v play off připisoval 29,1 bodů při 52,1% střelby a také 11,9 doskoků.

V dalších letech po roce 1990 si Malone pokaždé držel svá hvězdná čísla. V sezóně 1992-93 to bylo 27 bodů a 11,2 doskoků, v ročníku 1993-94 zase 25,2 bodů a 11,5 doskoků, sezónu 1994-95 Pošťák zakončil s průměry 26,7 bodů a 10,6 doskoků a ročník 1995-96 s 25,7 body a 9,8 doskoky. Rok 1992 byl něčím výjimečným - na Olympiádě ve španělské Barceloně totiž poprvé startovali profesionálové z NBA, slavný a doposud jedinečný Dream Team, a Karl Malone byl samozřejmě jeho součástí. Byl tak jedním z dvanácti hráčů, kteří na sebe mohli po skončení turnaje navléknout dosud asi nejcennější zlaté olympijské medaile z mezinárodních basketbalových turnajů. Na této Olympiádě také vyšel na světlo nesouhlas Malonea s - v té době už HIV pozitivním - navrátilcem do NBA, Magicem Johnsonem. Malone spolu s několika hráči prohlašoval, že Johnson by už nikdy hrát basketbal neměl, protože v případě otevřeného zranění při zápase by hrozila nákaza HIV ostatním hráčům či fanouškům. Navíc přilil do ohně i zvláštním vyjádřením, že je to vuči celé NBA a organizacím proti AIDS nefér, neboť při Magicově odchodu do sportovního důchodu se právě kvůli němu rozjely nejrůznější kampaně, které velebily aktivní účast vedení NBA na všech vyšetřeních a zákrocích, které Johnson proti této zákeřné nemoci podstoupil. NBA navíc po odchodu nemocné hvězdy vytvořila řadu opatření a vyšetření, které vedly k většímu bezpečí hráčů samotných. Právě proti Magicovým Lakers Malone v této sezóně překonal hranici 16 000 nastřílených bodů v kariéře, bylo to v den 4. února. V tomto roce se také odehrálo famózní All-Star střetnutí, kde Západ nakonec zvítězil nad Východem v prodloužení 135:132 a Karl Malone (28 bodů a 10 doskoků) zvedl nad hlavu trofej pro MVP tohoto zápasu spolu se svým velkým přítelem a spoluhráčem, Johnem Stocktonem.

V sezóně 1993-94 startovalo hvězdné křídlo ve všech 82 utkáních a pomohlo Jazz k druhému konferenčnímu finále v historii - a také ve své kariéře. Ve své deváté sezóně v lize si Malone připisoval 25,2 bodů na utkání, 11,5 doskoků, zblokoval celkem 126 střel a z pole střílel s úspěšností 49,7%. Na palubovce mu bylo dopřáno druhé největší porce minut z celé ligy (3 329) hned po nedostižném a také dosti kontroverzním Latrellu Sprewellovi. 29. března 1994 Malone doskočil své kariérní maximum 23 míčů, ale zároveň se mu v tomto utkání příliš střelecky nevedlo, když trefil jen 8 z 29 střel z pole a musel tak spolknout hořkou porážku 113:116 s Golden State. Po tomto zápase vyřkl Malone větu, kterou naznačil, že novináři si při takto slabém procentu střelby jeho 23 doskoků sotva všimnou. "Mé doskoky na zítřejší titulní straně novin nenajdete. Bude tam výčet všech těch snadných střel, které jsem dnes minul..." Pozdější šampión Houston Rockets vyřadil Jazz v bitvě o finále 4:1 na zápasy, když ani Malone, ani Stockton nenašli recept na famózní střeleckou mašinu Hakeema Olajuwona. Malone se však vyrovnal Olajuwonovi alespoň co se bodů v posledních čtvrtinách této série týkalo - tento vzájemný minisouboj dopadl 93:93.

Poprvé v historii klubu dosáhl Utah v sezóně 1994-95 60 výher v základní části, když zaznamenali i zajímavou a skvělou šňůru 15 vítězství na venkovních palubovkách za sebou, což je dodnes druhý nejlepší výkon svého druhu. Malone s 26,7 body na utkání obsadil čtvrtou pozici mezi střelci a stal se 19. hráčem historie NBA, který dosáhl hranice 20 000 nastřílených bodů. V tomto roce se však Jazz ve vyřazovacích bojích příliš nevedlo - stopku jim vystavil opět Houston, tentokrát však v prvním kole. A právě Houston vyhrál podruhé za sebou titul.

Po tomto dlouhém období deseti let Karl Malone prodloužil 13. ledna 1996 smlouvu s Utahem. Za celou tu dobu si kádr ze Salt Lake City zahrál dvakrát konferenční finále. V roce 1992, kdy podlehl Portlandu, v roce 1996, kdy jej zastavil Olajuwonův Houston a potřetí Jazz padli krůček před finále v sezóně 1995-96, kdy se sklonili před Seattlem SuperSonics. Až do této chvíle si však nikdy nezahráli přímý souboj o trofej Larryho O'Briena. Následující sezóny však měly tuto skutečnost změnit.