בפלייאוף, גברו הג'אז על יוסטון רוקטס בסיבוב הראשון, 3-2, ובחצי גמר המערב על הסן אנטוניו ספרס, 4-1, והתקדמות לסדרת גמר המערב עונה שלישית ברציפות. הג'אז, פגשו בסדרת גמר המערב את הלוס אנג'לס לייקרס בהנהגתו של שאקיל אוניל, הגארדים אדי ג'ונס, ניק ואן אקסל, וקובי בראיינט הצעיר. הג'אז קבעו את הטון בסדרה שכבר במשחק הראשון הביסו את הלייקרס 77–112. המשחק השני בסדרה היה צמוד בהרבה והסתיים בניצחון הג'אז, 99-95. שני המשחקים הבאים בסדרה התקיימו בלוס אנג'לס, והוכרעו בהפרש של 7.5 נקודות בממוצע. אך, גם בהם לא יכלו הלייקרס לג'אז הדומיננטיים, שניצחו בסדרה 0–4, מנחילים ללייקרס את ה"סוויפ" הראשון בסדרת פלייאוף, מאז סדרת הגמר ה-NBA של שנת 1989, ועולים בפעם השנייה ברציפות לסדרת גמר ה-NBA.
בסדרת הגמר של ליגת ה-NBA לעונת 1998, פגשו הג'אז שוב, כמו בעונה הקודמת, את האלופה שיקגו בולס בהנהגתו של מייקל ג'ורדן. הג'אז שנהנו מיתרון ביתיות על פני הבולס, ניצחו במשחק הראשון בסדרה, 88-85, לאחר הארכה, לאחר שסקוטי פיפן מהבולס החמיץ זריקת 3-נקודות בשניות האחרונות. במשחק השני בסדרה שנערך גם הוא בסולט לייק סיטי, הצליחו הבולס במהלך הרבע הרביעי לרוץ ולעלות ליתרון שהשתיק את הדלתא סנטר הגועש, ולנצח במשחק 88–93 ולגנוב לג'אז את יתרון הביתיות. במשחק השלישי בסדרה הביסו הבולס את הג'אז ב-42 נקודות יתרון, 96-54. הג'אז קבעו שיא שלילי עם כמות הנקודות הנמוכה ביותר בהיסטוריה של סדרות גמר ה-NBA מאז הכנסתו של שעון ה-24 שניות. המשחק הרביעי בסדרה היה צמוד לרוב אורכו, אך הג'אז נוצחו 82–86. דניס רודמן, שהחסיר אימונים בין המשחקים כדי להשתתף באירוע היאבקות מקצוענית, היה לגיבור הבלתי צפוי של המשחק, כשהוא קולע זריקות עונשין מכריעות וחוסם זריקה של קארל מלון בשניות הסיום של המשחק. הג'אז התאוששו במשחק החמישי וניצחו 81–83. מלון הציג את משחקו הטוב בסדרה עם 39 נקודות. במשחק השישי הצליחו הג'אז להחזיק ביתרון במשך רוב שלבי המשחק, אך הבולס הצליחו להתעלות ובשניות האחרונות של המשחק לעלות ליתרון מקליעה של ג'ורדן (שסיים את המשחק עם 45 נקודות) שנודעה לימים בשם "The last shot", שהבטיחה אליפות שלישית ברציפות לשיקגו בולס עם ניצחון, 87-86. בסדרה כולה ניצחו הבולס 4-2.
בעונת 99–1998, שקוצרה ל-50 משחקים עקב שביתת השחקנים, סיימו הג'אז במאזן 13–37 בתום העונה הסדירה, כשהם בשוויון עם סיאטל סופרסוניקס כמאזן הטוב בליגה. בסיבוב הראשון של הפלייאוף גברו הג'אז על סקרמנטו קינגס בחמישה משחקים. אך, בסיבוב השני נוצחו בידי פורטלנד טרייל בלייזרס, 4-2. למרות אכזבה נוספת, זכה קארל מלון בפרס ה-MVP של העונה הסדירה.
את עונת 00–1999, סיימו הג'אז במאזן 27–55 וזכו באליפות הבית המערב-תיכוני. אך, בפלייאוף התקשו כאשר הפסידו שוב בסיבוב השני לפורטלנד טרייל בלייזרס. במהלך הפגרה פרש ג'ף הורנסק והווארד איזלי הועבר בטרייד שכלל ארבע קבוצות והביא לג'אז את דונייל מרשל. בדראפט 2000 בחרו הג'אז בסיבוב הראשון כבחירה ה-23 את בוגר התיכונים ד'שון סטיבנסון.
בעונת 01–2000, הגיעו הג'אז למאזן 29–53 בתום העונה הסדירה, אך נכשלו בפלייאוף, לאחר שעלו ליתרון 0–2 בתום שני המשחקים הראשונים בסדרה, הפסידו הג'אז בשלושת המשחקים הבאים ונכנעו לדאלאס מאבריקס 2-3. הייתה זו ההדחה המוקדמת ביותר של הג'אז ממשחקי הפלייאוף מאז עונת 95–1994.
בעונת 02–2001, בחרו הג'אז בדראפט 2001 את אנדריי קירילנקו בסיבוב הראשון כבחירה ה-24. בעונת הרוקי שלו השיג קירילנקו 10.7 נקודות, 4.9 כדורים חוזרים, 2.91 חסימות בממוצע למשחק. הג'אז החלו לאט, והשיגה מאזן של 15–16 במהלך החודשיים הראשונים וסיימו במאזן 38–44 בתום העונה הסדירה. בסיבוב הראשון של הפלייאוף נוצחו הג'אז בידי סקרמנטו קינגס, 3-1.
קודם לעונת 03–2002, הועברו מרשל וראסל לקבוצות אחרות. הפורוורד מאט הארפרינג נרכש מפילדלפיה 76'. הוא נטל את עמדת הפורוורד הפותח ליד מלון והשיג 17.6 נקודות ו-6.6 כדורים חוזרים בממוצע למשחק, המספרים הטובים בקריירה שלו. הג'אז השיגו מאזן 35–47 בתום העונה הסדירה והתקדמו אל הפלייאוף. שם פגשו שוב את סקרמנטו קינגס להם הפסידו לאחר חמישה משחקים, 4-1.
לאחר העונה הגיע עידן לסיומו כאשר ג'ון סטוקטון פרש, וקארל מלון עזב כשחקן חופשי ללוס אנג'לס לייקרס.
2003–2006: בנייה מחדש.
עם עזיבתם של שתי אבני היסוד של המועדון, לפתע מצאו את עצמם הג'אז חסרי בסיס עם כניסתם לעונת 04–2003. הצפייה של כמה עיתוני NBA כולל המגזין ספורטס אילוסטרייטד הייתה כי יסיימו קרוב לתחתית הליגה. באופן מפתיע, הג'אז סיימו את העונה הסדירה במאזן 40–42. הקבוצה הציגה כמה שחקנים לא ידועים שהגיחו ונתנו תרומה משמעותית, כולל קירילנקו, ראג'ה בל, וקרלוס ארויו. במיוחד, אנדריי קירילנקו שהפגין את רב-גוניותו גם בהגנה וגם בהתקפה וזכה להיבחר למשחק האולסטאר. הג'אז החמיצו את הפלייאוף במשחק אחד לדנוור נאגטס, מסיימים רצף של 20 עונות בפלייאוף. ג'רי סלואן המאמן הראשי סיים במקום השני בתחרות מאמן השנה, כשהוא מפסיד ליובי בראון מממפיס גריזליס.
במהלך הפגרה, עשו הג'אז מהלכים שנועדו לשפר את הסגל המבוגר, כשרכשו את, קרלוס בוזר ומהמט אוקור כשחקנים חופשיים והחתימו מחדש את קרלוס ארויו וגורדן גיריצ'ק על הארכת חוזה.
עונת 05–2004 סומנה בעיקר על ידי סדרה של פציעות, תחילה ארויו וראול לופס, ומאוחר יותר בוזר וקירילנקו, שמילאו תפקיד מרכזי בנפילתם של הג'אז לתחתית הבית המערב-תיכוני. כאשר היה בריא, מילא בוזר בכישרון את תפקיד הפאוור פורוורד, כשהוא משיג 17.8 נקודות, 9.0 כדורים חוזרים בממוצע למשחק ב-51 משחקים. הג'אז סיימו את העונה הסדירה במאזן 26–56, הגרוע ביותר מאז עונת 82–1981.
בקיץ שנת 2005, המשיכו הג'אז לעצב את סגל השחקנים כאשר ביצעו טרייד על בחירות דראפט עתידיות כדי לקבל את הבחירה השלישית בדראפט 2005, אותה ניצלו כדי לבחור את דרן ויליאמס מאוניברסיטת אילינוי. עסקאות אחרות כללו את העברתו של ראג'ה בל לפיניקס סאנס, הג'אז החתימו מחדש את הסנטר גרג אוסטרטאג מסקרמנטו קינגס, והגארד הפצוע תדיר ראול לופס הועבר לממפיס גריזליס.
עונת 06–2005 הייתה מוכת פציעות עוד לפני שהחלה; בוזר החמיץ 49 משחקים וגורדן גיריצ'ק ואנדריי קירילנקו החמיצו גם הם מספר משמעותי של משחקים עקב פציעות. אוקור וקירילנקו, לעומת זאת, הראו משחק יעיל ועקבי. אך, בעלי הקבוצה לארי מילר הביע באופן עקבי את חוסר שביעות רצונו ממאמצי הקבוצה באותה העונה. הג'אז נשארו במירוץ לפלייאוף עד שלושה משחקים לסיומה של העונה הסדירה, כאשר הפסידו לדאלאס מאבריקס. הג'אז סיימו את העונה במאזן 41-41 רק שלושה משחקים ממקום המוביל לפלייאוף. אוסטרטאג פרש בסיומה של העונה, לאחר שבילה 10 מ-11 שנותיו ב-NBA במדי יוטה ג'אז.
בדראפט 2006, בחרו הג'אז כבחירה ה-14 את הקלע המבטיח רוני ברואר מאוניברסיטת ארקנסו. בסיבוב השני של הדראפט בחרו הג'אז את די בראון כבחירה ה-46 ואת פול מילסאפ כבחירה ה-47. כמה שחקנים צעירים הועברו לגולדן סטייט ווריורס תמורת דרק פישר, טרייד שנתן לג'אז רכז ותיק. כמה עיתוני ספורט גדולים היללו את הג'אז על בחירות דראפט טובות וביצוע מהלכים טובים במהלך הפגרה.
2006–2011: תקופת ויליאמס ובוזר.
במהלך עונת 07–2006, השתפרו הג'אז באופן משמעותי בהשוואה לעונות קודמות, כשהם מסיימים את העונה הסדירה במאזן 31–51. קרלוס בוזר נבחר לראשונה למשחק האולסטאר (אף על פי שהפסיד את המשחק עקב פציעה קלה). גם מהמט אוקור נבחר לראשונה למשחק האולסטאר. דרן ויליאמס פרץ בעונתו השנייה בליגה, כשהוא מסיים שלישי בליגה בכמות האסיסטים בממוצע למשחק עם 9.3 (אחרי סטיב נאש וכריס פול).
הג'אז פיתחו גם ספסל עמוק; בעשרת המשחקים שבוזר ואוקור (שני הקלעים המובילים) החמיצו, הצליחה הקבוצה להשיג מאזן 2–8. פול מילסאפ היווה הפתעה נעימה בעונת הרוקי שלו, כשהפך לגיבוי תחרותי לבוזר. למרות משחקם המשתפר של כוכבי הג'אז המנצחים, קירילנקו חווה ירידה משמעותית בממוצעיו ונראה כמתקשה להתאים עצמו לתפקידו המופחת בסגל השחקנים. דבר שהוביל להתפרקות, שזכתה לפרסום רב, בסיבוב הראשון של הפלייאוף.
בפלייאוף, פגשו הג'אז את יוסטון רוקטס בסיבוב הראשון, כמפגש של המדורגות רביעית וחמישית (כיוון שזכתה באליפות הבית הצפון-מערבי דורגה יוטה גבוה יותר, אך יוסטון סיימה את העונה במאזן טוב יותר, 52-30, בניגוד למאזנה של יוטה, 51-31, כך שיתרון הביתיות היה בידה של יוסטון. הסדרה התאפיינה במשחק פיזי, והייתה צמודה ברוב שלביה, כאשר שתי הקבוצות מצליחות לשמור על משחקי הבית שלהן בששת המפגשים הראשונים. הג'אז הצליחו לשבור מגמה זו במשחק השביעי בסדרה שהתקיים ביוסטון, כאשר גברו על הרוקטס 99–103. הג'אז המשיכו לסיבוב השני של פלייאוף המערב בו פגשו את המדורגת שמינית גולדן סטייט ווריורס, שבסיבוב הראשון הצליחו להדהים את המדורגת ראשונה דאלאס מאבריקס (שסיימה את העונה הסדירה במאזן 15–67, אחד הטובים בהיסטוריה של ה-NBA). אך, למרות החששות מפני הפתעה הצליחו הג'אז לטפל בקלות בסדרה מול הווריורס להדיחם לאחר חמישה משחקים, 4-1. בגמר המערב פגשו הג'אז את סן אנטוניו ספרס, אך לא הצליחו להתמודד עם הספרס המנוסים, כשהפסידו בחמישה משחקים, 4-1, למי שבסופו של דבר הפכה לאלופת ה-NBA.