עונה לאחר מכן, 1989-90, עם בובי האנסן שדחק את רגליו של דארל גריפית' כגארד הפותח לצידו של סטוקטון. גם ת'רל ביילי שהפך למניה בטוחה עם 19 נקודות בממוצע למשחק בעונה הקודמת, סבל מהפחתה במעמדו, כאשר הגארד הרוקי בלו אדוארדס שיחק תפקיד מרכזי בקו הקידמי. מייק בראון, הפורוורד-סנטר המחליף, החליף את מארק איטון בצורה תכופה יותר. התוצאה הייתה מאזן ניצחונות-הפסדים הטוב בהיסטוריה של הג'אז, כאשר הג'אז עולים למאזן 27–55 בסיומה של העונה הסדירה ומסיימים במקום השני לאחר סן אנטוניו ספרס שסיימו את העונה הסדירה במאזן 26–56. קארל מלון השיג את העונה הסטיסטית הטובה ביותר שלו, כשהוא קולע 31 נקודות, קולט 11.1 כדורים חוזרים בממוצע למשחק. ג'ו סטוקטון השיג 17.2 נקודות ו-14.5 אסיסטים בממוצע למשחק, שהיו גם שיאי קריירה, כאשר גם סך כל האסיסטים והממוצע העונתי שלהם היה הטוב בליגה. בפלייאוף, נקבע כי יפגשו עם פיניקס סאנס, בהובלתם של שחקני האולסטאר, טום צ'יימברס וקווין ג'ונסון. הסאנס הפתיעו את הג'אז כאשר גברו עליהם בחמישה משחקים, 2-3, בסיבוב הראשון. שוב, הג'אז נותרו עם השאלה, איך הם מצליחים כל כך במהלך העונה הרגילה אך נכשלים במשחקי הפלייאוף.
1990–1996 התקדמות ומאבק.
הג'אז החלו את עונת 91–1990 במאזן 15–22, לפני שמצאו את הקצב, והמשיכו במאזן 8–27 במהלך החודשים ינואר ופברואר, כאשר התוספת החדשה לסגל ג'ף מלון משיג 18.6 נקודות בממוצע למשחק באותה העונה, נותן לג'אז שלוש אופציות חזקות בטור הנקודות (קארל מלון, ג'ף מלון, וג'ון סטוקטון – שקלעו יחדיו 64.8 נקודות בממוצע מתוך 104 הנקודות שקלעו הג'אז בממוצע למשחק). הג'אז סיימו את העונה הסדירה במאזן 28–54, וסיימו במקום השני באזור המערב, משחק אחד אחרי סן אנטוניו ספרס, דומה למיקומם שתי הקבוצות בסיומה של העונה הקודמת. בפלייאוף, הם פגשו בפעם השנייה ברציפות את פיניקס סאנס בסיבוב הראשון, אך הפעם הג'אז היו מוכנים לקראתם. במשחק הראשון התפוצצו הג'אז על הסאנס, בפיניקס, אריזונה, 129-90, ונותנים את הטון לסדרה כולה, כאשר הג'אז גברו על הסאנס 1–3 לאחר ארבעה משחקים, וזוכים לעלות לסיבוב השני של הפלייאוף למפגש מול פורטלנד טרייל בלייזרס, אלופת המערב המגנה על כתרה. הג'אז שיחקו היטב, כאשר הם לא מאפשרים לבלייזרס לברוח במהלך המשחק, אך בסופו של דבר נכנעו והפסידו בסדרה 1–4 ובלייזרס בעלי הסגל העמוק והמנוסה יותר.
עונת 92–1991 התבררה כמוצלחת בהיסטוריה של המועדון, באותו הזמן. הג'אז עברו לאולם חדש הדלתא סנטר, אולם חדיש המכיל 19,911 מקומות ישיבה. אולם זה היווה שיפור משמעותי לעומת הסולט פאלאס המיושן, שאליו יכלו להיכנס מעט יותר מ-12,000 צופים וחסר יציעי כבוד וחלל להשכרה (שניהם מניבים כסף רב למועדון). מוקדם באותה עונה, טרייד הביא לקבוצה את טיירון קורבין, פורוורד הגנתי וקשוח, ממינסוטה טימברוולבס בתמורה לחביב האוהדים, ת'רל ביילי.
הג'אז סיימו את העונה הסדירה במאזן 27–55, וזכו בתואר אליפות הבית המערב-תיכוני לראשונה משנת 1989, וציפתה להתקדם שלב נוסף במשחקי הפלייאוף. במשחקי הפלייאוף, גברו הג'אז על לוס אנג'לס קליפרס, 3-2, בסיבוב הראשון, וגברו על סיאטל סופרסוניקס בסיבוב השני, 4-1, מתקדמים לראשונה לסדרת גמר המערב, שם פגשו את פורטלנד טרייל בלייזרס. שוב, הוכיחו הבלייזרס כי הם טובים יותר, כאשר גברו על הג'אז בשישה משחקים, 4-2 ומנעו מהג'אז נסיעה ראשונה לגמר ה-NBA.
עונת 93–1992 התבררה כאכזבה בהשוואה לשנים הקודמות, כאשר הג'אז מסיימים את העונה הסדירה במאזן 35–47 ובמקום השלישי במערב. עמדת הסנטר, שאוישה ברובה בידי מארק איטון במהלך העשור האחרון, הפכה לבעייתית, בשעה שאיטון התמודד עם פציעות וגילו המתקדם. נקודת האור של העונה הייתה אירוחו של משחק האולסטאר והאירועים הסובבים אותו במהלך סוף שבוע האולסטאר. הג'אז אכזבו בפלייאוף, כאשר הפסידו בסיבוב הראשון לסיאטל סופרסוניקס 2-3. במהלך הפגרה, טיפל המועדון בבעיית הסנטר כאשר פלטון ספנסר נרכש ממינסוטה, בתמורה לסנטר המחליף מייק בראון.
במהלך עונת 94–1993, העבירו הג'אז בטרייד את ג'ף מלון לפילדלפיה 76' ובתמורה קיבלו את ג'ף הורנסק. הורנסק היה מתואם היטב עם ג'ון סטוקטון, והג'אז התייצבו במאזן 29–53 בסיומה של העונה הסדירה, ודורגו במקום החמישי במערב. בפלייאוף, הם פגשו את סן אנטוניו ספרס, המדורגת רביעית, בסיבוב הראשון. בתצוגת הגנה מרשימה הצליחו הג'אז לעצור את כוכבם של הספרס, דייוויד רובינסון, שסיים כמלך הסלים של העונה הסדירה עם 29.8 נקודות בממוצע למשחק ב-50% הצלחה מהשדה, והורידו אותו ל-20 נקודות בממוצע למשחק ב-41% הצלחה מהשדה במהלך סדרת הפלייאוף. הג'אז גברו על הספרס בארבעה משחקים, 3-1, מוחקים תוך כדי את יתרון הביתיות של סן אנטוניו ספרס. בסיבוב השני, חצי גמר המערב, פגשו הג'אז את דנוור נאגטס הנחושים, שדורגו במקום השמיני במערב בסיומה של העונה הסדירה. הג'אז שנהנו מיתרון ביתיות עלו ליתרון 0–3 מבטיח, אך הנאגטס התאוששו ובנחישות הצליחו להשוות את הסדרה לאחר שישה משחקים, 3-3. במשחק השביעי והמכריע שנערך בדלתא סנטר שבסולט לייק סיטי, הג'אז התאוששו והצליחו לעצור את תנופת הנאגטס ולנצח במשחק, 91-81 ולהעפיל לגמר המערב, שם נוצחו 1–4 בידי מי שלבסוף הפכה לאלופת ה-NBA, יוסטון רוקטס, 4-1.
בעונת 95–1994, היה לסגל הג'אז עומק וניסיון הנחוצים, לדעת הפרשנים, להוות מתמודדת משמעותית על אליפות ה-NBA. אך, הג'אז איבדו את הסנטר הפותח פלטון ספנסר לאחר 34 משחקים לאחר שקרע את גיד אכילס. סגל השחקנים של הג'אז היה עמוק מספיק כדי להצליח ולסיים את העונה במאזן 22–60. אך, למרות זאת הפסידו הג'אז בסיבוב הראשון של הפלייאוף ליוסטון רוקטס, 3-2.
האיש הגדול גרג אוסטרטאג, צורף לקבוצה לקראת עונת 96–1995. הג'אז סיימו את העונה הסדירה במאזן 27–55, וסיימו את העונה הסדירה במקום השלישי במערב. בפלייאוף, גברו הג'אז על פורטלנד טרייל בלייזרס בסיבוב הראשון, 3-2, בסיבוב השני, חצי גמר המערב, גברו הג'אז על סן אנטוניו ספרס, 4-2, והעפילו לגמר המערב שנה שנייה ברציפות. בסדרת הגמר המערב, פגשו הג'אז את המדורגת ראשונה במערב, סיאטל סופרסוניקס, הסוניקס עלו ליתרון 0–2 בסדרה לאחר שני המשחקים הראשונים בסיאטל, במשחק השלישי שנערך בסולט לייק סיטי הצליחו הג'אז להתאושש ולזכות בניצחון ראשון בסדרה, 96-76. אך המשחק הרביעי שנערך גם הוא בסולט לייק סיטי, גברו הסוניקס על הג'אז, 86-88 ועצרו את מומנטום מהמשחק השלישי בסדרה. עתה כאשר הסוניקס ביתרון, 3-1 בסדרה, חזרה הסדרה למשחק החמישי בסיאטל, הג'אז התאוששו וגברו על הסוניקס, 98-95 והחזירו את הסדרה לסולט לייק סיטי, למשחק השישי. במשחק השישי בסדרה, התפוצצו הג'אז באולמם הביתי והביסו את הסוניקס 83–118. עתה נראה היה כי המומנטום נמצא בידיהם של הג'אז, כאשר הסדרה הגיעה למשחק השביעי והמכריע, בסיאטל. אך, הסוניקס התאוששו שוב, והצליחו לזכות בסדרה ההפכפכה, 4-3, לאחר שניצחו במשחק השביעי 86–90.
1996–2003: גמר ה-NBA והשנים האחרונות של מלון וסטוקטון.
בעונת 97–1996, השיגו הג'אז את המאזן הטוב ביותר בהיסטוריה של המועדון, 64-18, כשהם זוכים בתואר אליפות הבית המערב-תיכוני ובמאזן הטוב ביותר באזור המערב. הצלחת הקבוצה נתמכה בעיקר על ידי ג'ון סטוקטון, קארל מלון, וג'ף הורנסק, כמו גם על ידי ביירון ראסל, אנטואן קאר, הווארד איזלי, ושנדון אנדרסון. קארל מלון זכה בתואר ה-MVP של העונה הסדירה לעונת 97–1996, כשהוא משיג 27.4 נקודות, 9.9 כדורים חוזרים, ו-4.5 אסיסטים בממוצע למשחק.
בפלייאוף, פגשו הג'אז בסיבוב הראשון את המדורגת שמינית במערב, לוס אנג'לס קליפרס, וגברה עליהם 0–3. בחצי גמר המערב פגשו הג'אז את לוס אנג'לס לייקרס שסיימה את העונה הסדירה במקום הרביעי במערב, וגברו עליהם בחמישה משחקים, 4-1. בגמר המערב פגשו הג'אז את יוסטון רוקטס ולאחר שישה משחקים גברו עליהם 2–4 כאשר במשחק השישי סטוקטון קולע שלשת ניצחון. עתה העפילו הג'אז לסדרת גמר ה-NBA הראשונה בתולדותיהם, ובה פגשו את האלופה היוצאת שיקגו בולס בהובלתו של מייקל ג'ורדן. לאחר שנוצחו בשני המשחקים הראשונים בשיקגו, במשחק הראשון על ידי סל ניצחון של ג'ורדן, הצליחו הג'אז להתאושש ולנצח בשני המשחקים הבאים שהתקיימו בסולט לייק סיטי. הבולס הצליחו לגבור על הג'אז במשחק החמישי בסדרה שהתקיים אף הוא בסולט לייק סיטי, 88-90. עתה חזרה הסדרה לשיקגו, והג'אז לא הצליחו לעצור את הסחף ונוצחו שוב במשחק צמוד, 86-90, ניצחון שהעניק לשיקגו בולס את האליפות השנייה ברציפות.
במהלך הפגרה, ערכו הג'אז שינויים משמעותיים בסגל השחקנים. כאשר עונת 98–1997 קרבה, התעוררה הציפייה כי הג'אז יהפכו למועמדים לתואר האליפות שוב. אך, סטוקטון סבל מפציעת ברכיים קשה לפני שהחלה העונה, והחמיץ את 18 המשחקים הראשונים, בהן הג'אז השיגו מאזן של 7–11. לאחר חזרתו של סטוקטון, השיגו הג'אז מאזן של 13–51. הם סיימו את העונה הסדירה במאזן 20–62 וזכו באליפות הבית המערב-תיכוני. אף על פי שסיימו את העונה הסדירה עם מאזן זהה לאלופה, שיקגו בולס, החזיקו הג'אז ביתרון ביתיות לאורך הפלייאוף, מאחר שמאזן המפגשים בין הג'אז לבולס במהלך העונה הסדירה נטה לטובת הג'אז שנצחו את שני המפגשים ביניהן.