באטיסון הסיק כי המועדון לא יכול להיות בר-קיימא כל עוד הוא ישהה בניו אורלינס והחליט כי על המועדון לעזוב למקום אחר. לאחר שבדק כמה מקומות חדשים, הוא החליט לעבור לסולט לייק סיטי, וזאת אף על פי שהייתה שוק קטן בהשוואה לניו אורלינס באותו הזמן. אך, סולט לייק סיטי הוכיחה שהיא יכולה לתמוך בקבוצת כדורסל מקצוענית כאשר היא שימשה ביתם של יוטה סטארס מליגת ה-ABA משנת 1970 ועד שנת 1976. הסטארס זכו לפופולריות רבה בעיר, אך באופן בלתי מוסבר התמוטט מצבם הכלכלי בשתי עונותיהם האחרונות, והם התפרקו במהלך חודש דצמבר 1975, לאחר ששיחקו רק 16 משחקים בעונת ה-ABA האחרונה. אף על פי שסולט לייק סיטי לא נודעה בשל תרבות הג'אז שלה, החליטה הנהלת המועדון להשאיר את השם, כמו גם את צבעי המועדון המקורי ירוק, סגול, וזהב (צבעי פסטיבל המרדי גרא). היו שנפגעו מכך שהג'אז נשארו בשמם לאחר שעזבו את ניו אורלינס, כשהם מציינים כי ישנה כאן מטאפורה של גנבה של הג'אז משורשיו התרבותיים.
כמות הצופים של הג'אז ירדה במעט לאחר מעברם מניו אורלינס ליוטה, וזאת עקב קבלת אישור המעבר מאוחר (יוני 1979) ושיווק גרוע בעיר סולט לייק סיטי וסביבתה. הצעד הראשון, מיני רבים, אותו ביצעה הנהלת הג'אז היה טרייד שהביא לקבוצה את הקלע אדריאן דאנטלי תמורת ספנסר הייווד. במהלך עונת 80–1979 קלע דאנטלי 28 נקודות בממוצע למשחק, ונתן לקבוצה את האפשרות לנפות את מרוויץ' בתחילת העונה. הקבוצה השתרכה מאחור וסיימה את העונה הסדירה במאזן 24–58, אך כתוצאה ממיקום נמוך זה זכתה בבחירה השנייה בדראפט 1980, אותה ניצלו כדי לבחור את דארל גריפית' מאוניברסיטת לואיוויל, כחלק נוסף מהפאזל הנבנה במועדון.
במהלך עונת 81–1980, נאבק המועדון במגרש אך גם בבעיות כלכליות, אף על פי שבסגל השחקנים היו דאנטלי, שהפך לשחקן אולסטאר רב-שנתי, וגריפית' שהפך לקלעי של 20 נקודות בממוצע למשחק; כמו גם הרכז העולה ריקי גרין, לא הצליחו הג'אז להגיע למאזן חיובי וסיימו את העונה הסדירה במאזן 28–54. טום ניסאלק עזב את תפקיד המאמן הראשי לאחר שהקבוצה החלה את עונת 82–1981 במאזן 8–12, והג'נרל מנג'ר פרנק ליידן החליפו. תחילה, תקופת אימונו של ליידן לא הראתה כל שיפור, כאשר הג'אז המשיכו את העונה במאזן 17–45 וסיימו את העונה הסדירה במאזן 25–57.
בדראפט 1982, בחרו הג'אז בבחירה הראשונה את דומיניק וילקינס, אך שילוב בין בעיות תזרים מזומנים של המועדון כמו גם סירובו של וילקינס לשחק ביוטה, הביא את המועדון לבצע טרייד עליו, חודשים ספורים לאחר הדראפט. בתמורה לזכויות על וילקינס העבירה אטלנטה הוקס את הגארדים ג'ון דרו ופרימן ויליאמס, ועוד מיליון דולר במזומן.
בעונת 83–1982 החמיץ דאנטלי 60 מתוך 82 המשחקים עקב פציעה, שולל מהג'אז את הקלע המוביל שלהם למשך רובה של העונה. גם הרכש החדש, ג'ון דרו, החמיץ חלק מהעונה, כשהוא משחק רק 44 משחקים במהלכה. בסופו של דבר הובילו את הג'אז דארל גריפית' עם 22.2 נקודות, ריקי גרים עם 14.3 נקודות, דני שייס 12.4 נקודות בממוצע למשחק. מארק איטון, סנטר המתנשא לגובה 2.24 מטר, בעונת הרוקי שלו החל לאייש את עמדת הסנטר של הג'אז. הג'אז סיימו את העונה הסדירה במאזן 30–52, עדיין מחוץ לפלייאוף, אך מהווה שיפור לעומת המאזן בסיום העונה הקודמת.
במהלך דראפט 1983, ניצלו הג'אז כדי לבחור את ת'רל ביילי כבחירה השביעית מאלופת ה-NCAA לשנת 1983 אוניברסיטת המדינה של קרוליינה הצפונית, ובשלב מאוחר יותר לקחו את בובי האנסן מאוניברסיטת איווה כבחירה ה-54.
עונת 84–1983 נפתחה בחוסר ודאות. המועדון הפסיד כסף, כאשר ההנהלה מתמרנת במיומנות, כמו לשחק את חלק ממשחקי הבית בלאס וגאס, כדי לעזור למועדון להפוך לריווחי יותר. נפוצו שמועות כי המועדון יעזוב את יוטה, בעקבות השוק הקטן ומאבקים כלכליים בין בעלי המועדון. אך, מזלה של הקבוצה על המגרש המשיך להשתפר, עם אדריאן דאנטלי הכשיר, ג'ף וילקינס, והרוקי ת'רל ביילי בעמדת הפורוורד, מארק איטון וריץ' קיילי התחלקו ביניהם באיוש עמדת הסנטר, וריקי גרין יחד עם דארל גריפית' בעמדת הגארד, וג'ון דרו שסיפק 17 נקודות לערב מהספסל. הג'אז השיגו 37–45 בסיומה של העונה הסדירה וזכו באליפות הבית המרכז-מערבי, תואר אליפות הבית הראשון בהיסטוריה של הג'אז.
לאחר שהתקדמו למשחקי הפלייאוף, גברו הג'אז על דנוור נאגטס 3-2 בסיבוב הראשון של הפלייאוף, והתקדמו לשחק מול פיניקס סאנס בחצי גמר המערב. אף על פי שנהנו מיתרון ביתיות בסדה של הטוב משבעה משחקים, הפסידו הג'אז לסאנס המנוסים בשישה משחקים 2–4.
חודש לאחר מכן לא היו אוהדי הג'אז שבעי רצון, כאשר הקבוצה בחרה רכז אלמוני בסיבוב הראשון של דראפט 1984, ג'ון סטוקטון מאוניברסיטת גונזגה. אוהדי הג'אז שהגיעו למסיבת הדראפט הביעו את מורת רוחם בקריאות בוז לבחירה.
1984–1988: תחילת עידן סטוקטון ומלון.
עונת 85–1984 חזתה בעלייתו של מארק איטון ככוח הגנתי. כשהוא משיג 5.56 חסימות בממוצע למשחק, יחד עם 9.3 נקודות ו-11.3 כדורים חוזרים בממוצע למשחק, כשהא זוכה בתואר שחקן ההגנה של העונה. מהצד השלילי, ג'ון דרו שיחק רק 19 משחקים במהלך העונה, ושולל מהקבוצה קלעי בתפקיד השחקן השישי. למרות זאת, הג'אז הצליחו להעפיל שוב למשחקי הפלייאוף, כשהם פוגשים בסיבוב הראשון את יוסטון רוקטס וכוכביהם האקים אולאג'ואן ורלף סמפסון. הג'אז הצליחו לגבור על הרוקטס בסדרה, 3-2, והתקדמו לחצי גמר המערב, ופגשו את דנוור נאגטס, הג'אז לא הצליחו לשלוט בסדרה ונוצחו בחמישה משחקים, 4-1.
חוסר היציבות הכלכלית של המועדון התייצבה באופן חלקי במהלך חודש אפריל 1985, כאשר לארי מילר רכש 50% מהמועדון תמורת 8 מיליון דולר, והפך לשותף לסאם באטיסטון, שחיפש להעביר את המועדון מיוטה. בדראפט 1985, צרפו הג'אז את קארל מלון מאוניברסיטת לואיזיאנה טק כבחירה ה-13, פאוור פורוורד המתנשא לגובה 2.06 מטר.
למלון הייתה השפעה מידית על הקבוצה בעונת 86–1985, כשהוא קולע בממוצע 14.9 נקודות וקולט 8.9 כדורים חוזרים בממוצע למשחק. מוסיף לדאנטלי הקו ההתקפה. אך, הגארד הפותח דארל גריפית' החמיץ את העונה כולה עקב שברי מאמץ, והקבוצה סובבה סביב 50% הצלחה ברובה של העונה. במשחקי הפלייאוף, הודחו הג'אז בסיבוב הראשון לאחר שנוצחו בידי דאלאס מאבריקס 3-1.
במהלך פגרת שנת 1986, קיבל סאם באטיסטון פנייה למכור את חלקו במועדון למארב וולפסון והארווי ראת'ר, שהיו מעוניינים להעביר את המועדון למיניאפוליס, מינסוטה. לארי מילר לא היה מעוניין למכור את חלקו במועדון, אך בעקבות סעיפים שונים בחוזה שלו עם באטיסטון הייתה למשקיעים החדשים אפשרות לרכוש גם את חלקו במועדון גם אם הוא יסרב למכור. במהלך תהליך ההתדיינות עלה מחיר המועדון עד ל-28 מיליון דולר (שוויים של הג'אז הוערך ב-16 מיליון דולר, כאשר רק שנה קודם לכן רכש מילר מחצית מהמועדון ב-8 מיליון דולר). ברגע האחרון נכנס גם מילר למשא ומתן ורכש את המחצית השנייה של המועדון תמורת 14 מיליון דולר, כשהוא קונה למעשה את החוזה המקורי עם באטיסטון, והשאיר את המועדון ביוטה. מאוחר יותר הפכו וולפנסון וראת'ר למייסדים של מינסוטה טימברוולבס, קבוצת הרחבה של הליגה, שכמעט נמכרה והועברה לניו אורלינס בשנת 1994.
עונת 87–1986 הייתה עונה של שינוי. כוכב הקבוצה, אדריאן דאנטלי, שנשא את הקבוצה על כתפיו בשנים הראשונות ביוטה, הועבר בטרייד לדטרויט פיסטונס תמורת קלי טריפיוקה, שחלק את העמדה עם ת'רל ביילי. ג'רלד גריפית', שחזר מסדרת פציעות שגרמה לו להפסיד את עונת 86–1985, איבד את מקומו בחמישייה הפותחת לבובי האנסן. ג'ון סטוקטון, בילה יותר זמן על הספסל מאשר ריקי גרין בעמדת הרכז הפותח. בינות לכל השינויים האלה, סיימה הקבוצה את העונה הסדירה במאזן 38–44, והפסידה לגולדן סטייט ווריורס בסיבוב הראשון של הפלייאוף.
בעונת 88–1987, תפס ג'ון סטוקטון את תפקיד הרכז הפותח לפני ריקי גרין, וקארל מלון התחיל לבסס את עצמו כאחד הפאוור פורוורדים הטובים בליגה. באותה שנה, סיימו הג'אז את העונה הסדירה במאזן 35–47 וגברו על פורטלנד טרייל בלייזרס הסיבוב הראשון של הפלייאוף בתוצאה 1–3, זוכים להיפגש בחצי גמר המערב מול האלופה היוצאת לוס אנג'לס לייקרס. לאחר שהלייקרס ניצחו במשחק הראשון בלוס אנג'לס, הפתיעו הג'אז כשגברו על הלייקרס במשחק השני, 101-97, בלוס אנג'לס, ועלו ליתרון בסדרה, 2-1, לאחר נצחו במשחק השלישי בסולט לייק סיטי. הג'אז הפסידו בשני המשחקים הבאים, 4 ו-5, אך נלחמו חזרה והביסו את הלייקרס במשחק השישי בסדרה, 108-80 שהשווה את לתוצאה 3-3. במשחק השביעי והמכריע, הצליחו הלייקרס לגבור על הג'אז 98–109. אך סדרה זו הוכיחה כי הג'אז הם כוח שיש להתחשב בו במאבקי הפלייאוף, שלא כמו בשנים הראשונות.
1988–1990: תחילת עידן ג'רי סלואן.
במהלך עונת 89–1988, פרש פרנק ליידן מתפקיד המאמן הראשי של יוטה ג'אז לאחר 17 משחקים מתחילת העונה, והוחלף בידי ג'רי סלואן. הג'אז הצליחו לנצח 51 משחקים ולזכות באליפות הבית המערבי-תיכוני. מלון וסטוקטון כמו גם מארק איטון, נבחרו למשחק האולסטאר. איטון זכה בפרס שחקן ההגנה של העונה בפעם השנייה, ונראה היה כי הג'אז מוכנים לקחת את הצעד הבא במשחקי הפלייאוף, לאחר שדחקו את לוס אנג'לס לייקרס לשבעה משחקים מתישים בעונה הקודמת. אך, האכזבה לא אחרה להגיע בפלייאוף, כאשר הם נוצחו 0–4 בידי המדורגת שביעית (הג'אז היו מדורגים במקום השני) גולדן סטייט ווריורס, 0-3, בסיבוב הראשון, ומסיימים באופן מפתיע את העונה של הג'אז.