כבר בעונתו הראשונה בדאלאס (עונת השביתה-המקוצרת ), התבסס נאש כשחקן מוביל בקבוצה ופתח בחמישייה בכל 40 המשחקים בהם שותף. עד לסיום העונה קבע ממוצעים של 7.9 נקודות, 5.5 אסיסטים ו-2.9 כדורים חוזרים למשחק. עם זאת, דאלאס כשלה בניסיונה להעפיל לפלייאוף. עם פתיחת עונת נפצע נאש בקרסול והושבת למשך חודשיים. עם חזרתו לפעילות, שיפר משמעותית את יכולתו ואף הציג שישה משחקי דאבל-דאבל בחודש האחרון של העונה. בסך הכל סיים את העונה עם ממוצעים של 8.6 נקודות ו-4.9 אסיסטים למשחק. דאלאס, אותה הובילו בעונה זו דניס רודמן, דירק נוביצקי ומייקל פינלי, השתפרה משמעותית לעומת העונה הקודמת, אך עם זאת, שוב לא הצליחה להעפיל לפלייאוף.
בעונת , קבע נאש ממוצעים של 15.6 נקודות ו-7.3 אסיסטים למשחק, בעונת הפריצה שלו בליגה. כאשר נאש מרכז את המשחק בצורה מעולה, נוביצקי ופינלי מציגים יכולת שיא ושחקן הרכש ג'וואן האוורד משלים, דאלאס הצליחה להעפיל לפלייאוף מהמקום השישי בליגה והגיעה עד לחצי גמר המערב, שם הודחה על ידי סן אנטוניו ספרס. בעונת , קבע נאש ממוצעי שיא של 17.9 נקודות ו-7.7 אסיסטים. הוא נבחר לראשונה בקריירה להשתתף במשחק האולסטאר ונבחר לחמישיית העונה השלישית. כאולסטאר, זכה נאש לתשומת לב רבה מגופי תקשורת והחל להתפרסם גם בקרב אוהדי הקבוצות האחרות. יחד עם נוביצקי ופינלי היה חלק מה"שלישייה הגדולה" של דאלאס. גם בעונה זו הצליחה דאלאס להעפיל לפלייאוף, אך שוב הודחה בחצי גמר המערב, הפעם על ידי סקרמנטו קינגס.
בעונת , כמעט והעתיק את העונה הקודמת מבחינה אישית. הוא קבע 17.7 נקודות ו-7.3 אסיסטים למשחק, ושוב נבחר למשחק האולסטאר ולחמישיית העונה השלישית. נאש ונוביצקי הובילו את דאלאס ל-14 ניצחונות רצופים עם פתיחת העונה ולחלוקת המקום הראשון בליגה בסיום העונה הסדירה יחד עם סן אנטוניו ספרס, כאשר לשתי הקבוצות מאזן זהה של 60 ניצחונות לעומת 22 הפסדים בלבד. בפלייאוף הגיעה דאלאס עד לגמר המערב אך הודחה על ידי סן אנטוניו ספרס, שהמשיכה לגמר ה-NBA ולבסוף זכתה באליפות. בדרכה לגמר הדיחה דאלאס את פורטלנד טרייל בלייזרס וסקרמנטו קינגס. בעונת , בעקבות רכישתם של אנטואן ווקר ואנטואן ג'יימיסון וריבוי שחקני ההתקפה בדאלאס ירד נאש בכמות הנקודות שקלע לעומת העונה הקודמת. בעקבות זאת לא זומן למשחק האולסטאר ולא נבחר לאחת מחמישיות העונה, על אף שקבע שיאי קריירה באסיסטים למשחק (8.8) ובאחוזים מקו העונשין (91.6%). בפלייאוף, לא הצליחו נאש ודאלאס לעבור את הסיבוב הראשון והודחו שוב על ידי סקרמנטו קינגס.
לאחר עונת , הפך נאש לשחקן חופשי והחל לנהל משא ומתן עם בעליה של דאלאס, מארק קיובן על חתימת חוזה ארון טווח. קיובן ביקש לשמר את כספי הקבוצה כדי שיוכל להחתים את דירק נוביצקי עם סיום חוזהו ולכן לא רצה להסתכן בהחתמתה של נאש על חוזה ארוך טווח. הצעתו של קיובן בסופו של דבר הייתה חוזה לארבע שנים בשווי 36 מיליון דולר, עם אופציה לשנה נוספת. קבוצתו הקודמת של נאש, פיניקס סאנס הציעה לשחקן חוזה לשש שנים בשווי 63 מיליון דולר. נאש, שבתחילה הסתייג מעזיבה ניגש לקיובן וניסה לשכנעו להשלים את הפערים בין ההצעות, משלא הסכים, החליט השחקן לחתום בפיניקס לאחר שש עונות בדאלאס. לאחר שזכה בשני תוארי MVP של העונה הסדירה בשתי העונות הבאות בפיניקס, התראיין קיובן בתוכנית המאוחרת עם דייוויד לטרמן ב-14 ביוני 2006 ואמר: "...אתה יודע שסטיב הוא אדם נפלא ואני אוהב אותו, אך למה הוא לא שיחק כמו MVP עבורנו?".
החזרה לפיניקס (2004–2012).
בפיניקס חבר נאש לשלישיית הצעירים המבטיחה, שון מריון, ג'ו ג'ונסון ואמארה סטודמאייר. את העונה שלפני הגעתו סיימו פיניקס עם מאזן רע במיוחד של 53-29, ובקבוצה התכוננו לעונה גרועה נוספת. מאמן הקבוצה מייק ד'אנטוני, הנחיל גישת משחק זריזה וכשרונית; הוא ביקש שחקנים אתלטיים שיכולים לצאת מהר להתקפות מתפרצות ולקלוע גם מטווחים רחוקים מהסל. הזדהותו של נאש עם שיטת המשחק האתלטית חיברה אותו באופן מצוין לשאר חבריו לקבוצה והוא הוביל את פיניקס למאזן הטוב בליגה (20–62) ולקליעה ממוצעת של למעלה מ-110 נקודות למשחק, הנתון הגבוה ביותר בליגה מזה עשור. כתוצאה מכך, נאש מסר 11.5 אסיסטים בממוצע (מלך האסיסטים) וקלע בלמעלה מ-50 אחוזי קליעה מהשדה ולמעלה מ-43 אחוזי הצלחה מטווח השלוש בעונה הסדירה. הוא זכה בתואר ה-MVP של העונה הסדירה לאחר שהקדים במספר ההצבעות את שאקיל אוניל. בכך הפך לקנדי הראשון שזוכה בתואר ולרכז הרביעי בהיסטוריה שמוכתר כ-MVP, לאחר שמג'יק ג'ונסון, בוב קוזי ואוסקר רוברטסון עשו זאת לפניו. בסיבוב הפלייאוף הראשון, פיניקס הדיחה את ממפיס גריזליס לאחר ארבעה משחקים ובסיבוב השני הוגרלה לשחק נגד קבוצתו הקודמת של נאש, דאלאס מאבריקס. נאש הוביל את פיניקס לניצחון 2–4 בסדרה, ולראשונה מאז 1993 להעפלה לגמר המערב, שם הפסידו הסאנס לאלופה הנכנסת סן אנטוניו ספרס בחמישה משחקים.
בעונה הבאה, ספג סטודמאייר פציעת ברך חמורה וג'ונסון וקוונטין ריצ'רדסון הועברו בעסקה. פיניקס לא ציפתה לשחזר את הישגיה ויכולתה מהעונה הקודמת, אך כאשר נאש מציג את אותה רמת משחק גבוהה, הגיעה הקבוצה למאזן מכובד של 28–54 וזכתה באליפות המחוזית. פיניקס הייתה שוב לקבוצה שקולעת את מספר הנקודות הגבוהה ביותר בממוצע עם שבעה שחקנים שקולעים למעלה מ-10 נקודות בממוצע, ונאש נבחר לראשונה בקריירה לפתוח בחמישיית המערב במשחק האולסטאר לשנת 2006. הוא קבע שיאי קריירה בנקודות (18.8), כדורים חוזרים (4.2), אחוזי קליעה מהשדה (51.2) ואחוזי קליעה מקו העונשין (92.1 - ראשון בליגה) ושוב הוביל את הליגה באסיסטים עם 10.5 בממוצע. כמו כן, נבחר בפעם השנייה ברציפות ל-MVP של העונה הסדירה. בסיבוב הראשון בפלייאוף, נאש ופיניקס חזרו מפיגור 1–3 נגד לוס אנג'לס לייקרס וניצחו בסדרה 3–4. בחצי גמר המערב הוגרלו להתמודד נגד לוס אנג'לס קליפרס, ושוב ניצחו בסדרה רק לאחר שבעה משחקים. למרות העונה המצוינת שעברה עליו, שוב נכשל נאש בהובלת פיניקס לגמר ה-NBA, לאחר שבפעם השנייה ברציפות הודחה הקבוצה בגמר המערב על ידי דאלאס מאבריקס.
גם עונת הייתה מצוינת עבור נאש שקבע ממוצעים של 18.6 נקודות ושיא קריירה של 11.6 אסיסטים למשחק והפך לראשון מאז מג'יק ג'ונסון בעונת 1990/1991 שקובע למעלה מ-18 נקודות ו-11 אסיסטים בממוצע למשחק בעונה הסדירה. הוא קיבל את מספר הקולות הגדול ביותר לחמישיית העונה, אליה נבחר יחד עם חברו לקבוצה סטודמאייר; השניים הפכו לחברים לקבוצה הראשונים שנבחרים יחד לחמישיית העונה מאז קובי בראיינט ושאקיל אוניל בעונת . למרות זאת, לא נבחר ל-MVP של העונה הסדירה לאחר שסיים במקום השני בבחירות לתואר עם 44 הצבעות, אחרי חברו לשעבר בדאלאס דירק נוביצקי שקיבל 83 הצבעות. בפלייאוף, הדיחה פיניקס את לוס אנג'לס לייקרס לאחר חמישה משחקים, אך לא הצליחה לעבור את סן אנטוניו ספרס בחצי גמר המערב והפסידה בסדרה 2–4.
נאש שותף ב-81 משחקים במהלך העונה הסדירה של עונת . ב-31 בינואר 2008 זומן נאש למשחק האולסטאר בפעם השישית בקריירה שלו. באמצע העונה הועבר שון מריון בעסקה למיאמי היט ולפיניקס הגיע שאקיל אוניל שזכה בארבע אליפויות NBA לפני כן. בעונה זו היה המחוז המערבי תחרותי במיוחד ועל אף יכולת טובה שהציגו נאש וחבריו לקבוצה, פיניקס עלתה לפלייאוף מהמקום השישי בלבד לאחד שסיימה את העונה הסדירה במאזן 27–55. בסיום העונה נבחר נאש לחמישיית העונה השנייה לעונה זו. למרות צירופו של אוניל, שהגיע במטרה לסייע לנאש וסטודמאייר להוביל את פיניקס לגמר ה-NBA, הודחה הקבוצה כבר בסיבוב הראשון בפלייאוף על ידי סן אנטוניו, שהדיחה אותה שוב, בפעם השלישית בארבע השנים האחרונות. במהלך המשחק החמישי בסדרה כאשר סן אנטוניו ביתרון 1–3, איבד נאש שני כדורים מכריעים בשתי הדקות האחרונות של המשחק, שעד לאיבודים היה צמוד ביותר ולמעשה חרץ את גורל הסדרה.
לקראת עונת הוחלף המאמן ד'אנטוני בטרי פורטר, שבשונה מקודמו העדיף את שיטת הכדורסל ה"מסורתית". נאש וחבריו לפיניקס התקשו לשחק היטב תחת שיטת המשחק החדשה ואפילו העסקה שביצעה הקבוצה במהלך חודש דצמבר, במסגרתה הועברו רג'ה בל ובוריס דיאו לשארלוט בובקאטס תמורת ג'ייסון ריצ'רדסון לא סייעה ליכולת הקבוצתית החלשה. לבסוף הוחלף פורטר באלווין גנטרי במהלך חודש פברואר, אך גם זה לא סייע לפיניקס. לראשונה מאז חזרתו של נאש, הקבוצה לא הצליחה להעפיל לפלייאוף.
את עונת , פתחו נאש ופיניקס בצורה מעולה ותשעה משחקים מפתיחת העונה עמדו על מאזן 1–8, כאשר נאש מציג שני משחקים של 20 אסיסטים. ב-21 בינואר 2010, נבחר נאש לפתוח שוב בחמישיית נבחרת המערב במשחק האולסטאר, אך נבחרתו הפסידה במשחק לנבחרת המזרח. בהובלתם של נאש וסטודמאייר דורגה פיניקס במקום הראשון בקליעת נקודות, עונה החמישית ברציפות, ושבה לפלייאוף לאחר שסיימה את העונה הסדירה במקום השלישי במערב עם מאזן 28–54. גם בפלייאוף המשיכה פיניקס ביכולת הקבוצתית הטובה ועם יכולת טובה של בדמותם של ריצ'רדסון וגרנט היל הוותיק, ניצחה את פורטלנד טרייל בלייזרס 2-4 בסיבוב הראשון והדיחה את סן אנטוניו ספרס ב בחצי גמר המערב. בגמר המערב, פגשה פיניקס את האלופה, לוס אנג'לס לייקרס. לאחר שני הפסדי חוץ, שבה פיניקס לביתה והשוותה את תוצאת הסדרה ל-2-2, אך למרות זאת הפסידה בשני המשחקים הבאים ובסדרה כולה.