Poslední sezóny v NBA (98-04)

Sezóna 1998-99 byla postižena výlukou, a tak se výrazně zkrátila. Jazz dosáhli bilance 37-13 a Karl Malone získal svou druhou cenu MVP, tedy trofej Maurice Podoloffa. Ve druhém kole play off však byli vyřazeni Portlandem a na příští léta definitivně vypadli z nejužšího okruhu každoročních uchazečů o titul. Zápas č. 5 v této sérii Jazz vyhráli 88:71, snížili na 2:3 a na utkání č. 6 se zajíždělo do Portlandu. Zde Malone opět ukázal, jak ostré má lokty, a jeho řádění tentokrát odnesl Brian Grant. Malone byl opět potrestán pokutou. V posledních letech s Jazz si připisoval postupně střelecké průměry 25,5 bodů na zápas a posléze 23,2, 22,4 a 20,6. Sezóna 2002-03 však pro utahského forwarda byla něčím výjimečným. Dostal se totiž na druhou příčku historické střelecké tabulky a překonal tak Wilta Chamberlaina, tedy hráče, který doposud je jediným na světě, který kdy v utkání NBA dokázal vstřelit 100 bodů. Rok 2003 je však černě zapsán v srdcích všech skalních Jazzmanů - John Stockton ukončil svou velkou kariéru a Karl Malone se stal volným hráčem s tím, že do Utahu se již nevrátí. Nejproduktivnější duo všech dob se tak rozpadlo a Malone chtěl zamířit někam, kde bude mít v posledním roce kariéry větší šanci získat svůj jediný možný titul. Za dobu v Utahu tým pokaždé dovedl k více než 50 výhrám v sezóně (s výjimkou ročníku 1992-93) a spolu se Stocktonem se stali nesmrtelnou dvojicí, která společně odehrála nejvíce utkání za jeden tým.

Konec kariéry s Lakers (03-04)

Karl Malone v NBA strávil ještě jednu sezónu, a to v Los Angeles Lakers. Zde chtěl naplnit svůj sen o titulu, ale ten se mu opět bohužel nesplnil. Lakers totiž ve finále podlehli defenzivnímu Detroitu Pistons a Malone tuto sérii odehrál z důvodu zranění jen částečně. Na první čtyři utkání nastoupil s velkým sebezapřením a v zápase č. 5 už se na nezdar svých spoluhráčů díval pouze z lavičky.

Po této sezóně se stal slavný Jazzman opět volným hráčem, do Lakers se však znovu vrátit nechtěl především kvůli osobním neshodám s Kobem Bryantem. Byl po operaci kolena a spekulovalo se, zdali vůbec ještě někde smlouvu podepíše. O jeho angažování měli zájem New York Knicks a později také San Antonio Spurs, 13. února 2005 však Malone na tiskové konferenci v Delta Center oznámil, že NBA po devatenácti letech opouští nadobro.