בעונה הבאה, , הוחזר נוביצקי לעמדת הפאוור פורוורד והמשיך לשפר את יכולתו, כאשר השיג ממוצעים של 21.8 נקודות, 9.2 ריבאונדים ו-2.1 אסיסטים למשחק. באותה עונה הוא קלע 151 שלשות וחסם 101 חסימות, ובכך הפך לשחקן השני בתולדות ה-NBA, אחרי רוברט הורי, שמשיג 100 ומעלה בכל אחד משני מדדים אלו בעונה. כתוצאה מחשיבותו הרבה לקבוצה מונה נוביצקי במהלך העונה לקפטן של דאלאס בצוותא עם מייקל פינלי. יחד עם פינלי הוא היה אחד משני שחקנים בקבוצה שפתחו בחמישייה בכל 82 המשחקים, ובעשרה משחקים שונים קלע 30 נקודות ומעלה. בסיום העונה נוביצקי נבחר לתואר החמישייה השלישית של העונה, ובכך הפך לשחקן הראשון בתולדות דאלאס שנבחר לאחת מחמישיות העונה. יחד עם הרכז האיכותי סטיב נאש ועם הקלע המצטיין פינלי, היה נוביצקי חלק מ"השלישייה הגדולה" של דאלאס.
באותה עונה סייע נוביצקי לדאלאס להשיג מאזן של 53 ניצחונות ו-29 הפסדים בסיום העונה הסדירה ולהעפיל לפלייאוף לראשונה מאז 1990. כמדורגת חמישית פגשה דאלאס את יוטה ג'אז. נוביצקי התמודד בסדרה זו מול כוכביה של יוטה, קארל מלון וג'ון סטוקטון, ולאחר הפסדי קבוצתו בשני המשחקים הראשונים קלע 33 נקודות הן במשחק השלישי והן במשחק הרביעי. במשחק החמישי ניצחה הקבוצה כתוצאה מסל ניצחון של קלווין בות' 9.8 שניות לסיום, והעפילה לחצי גמר המערב מול סן אנטוניו ספרס. נוביצקי התקשה בהתמודדות עם פורוורד סן אנטוניו, טים דאנקן, וקבוצתו הפסידה בשלושת המשחקים הראשונים בסדרה. לאחר ניצחון במשחק הרביעי הצטיין נוביצקי עם 42 נקודות ו-18 ריבאונדים במשחק החמישי, מה שלא מנע את הפסד קבוצתו בתוצאה 87–105 והדחתה מהפלייאוף.
לפני עונת חתם נוביצקי על חוזה חדש בדאלאס שתוקפו שש שנים תמורת 90 מיליון דולר. הוא השיג בעונה זו ממוצעים של 23.4 נקודות ו-9.9 ריבאונדים למשחק, ובעקבות יכולתו הטובה נבחר להשתתף לראשונה במשחק האולסטאר של ה-NBA וכן לחמישייה השנייה של העונה. בסדרת סיבוב הפלייאוף הראשון, מול מינסוטה טימברוולבס, התגבר נוביצקי על כוכב היריבה קווין גארנט כאשר קלע 33.3 נקודות בממוצע לעומת 24 של גארנט, וסייע לדאלאס לנצח בתוצאה 0–3. בשלב הבא, מול סקרמנטו קינגס, נוביצקי כשל מול השמירה הכפולה שהפעילו עליו הידו טורקוגלו וכריס ובר ודאלאס הודחה לאחר חמישה משחקים. על אף ההדחה נבחר נוביצקי ברוב גדול לזכייה בפרס יורוסקאר לכדורסלן האירופי של השנה, לאחר שהקדים בהצבעה את דיאן בודירוגה ואת פג'ה סטויאקוביץ' מסקרמנטו.
נוביצקי היה חלק חשוב בפתיחה המצוינת של דאלאס לעונת עם 11 ניצחונות רצופים. יכולתה המצוינת של הקבוצה התבטאה בבחירתו המשותפת, יחד עם נאש ופינלי, לתואר שחקן החודש במערב בנובמבר 2002 מטעם הנהלת הליגה. באותה עונה הגיע לממוצעי שיא בקריירה שלו, של 25.1 נקודות, 9.9 ריבאונדים ושלושה אסיסטים, והיה לאירופי הראשון בתולדות ה-NBA שקולע למעלה מ-2,000 נקודות בעונה. הוא הוביל את דאלאס לעונה הטובה בתולדותיה עד אז עם מאזן של 60 ניצחונות ו-22 הפסדים, ונבחר שוב למשחק האולסטאר ולחמישיית העונה השנייה. בסדרת סיבוב הפלייאוף הראשון, מול פורטלנד טרייל בלייזרס, קלע נוביצקי שלשה חשובה 90 שניות לסיום המשחק השביעי שסייעה לניצחון קבוצתו. נוביצקי הצטיין גם בסדרת הסיבוב השני, מול סקרמנטו קינגס, והוביל את דאלאס להעפלה לגמר המערב מול סן אנטוניו ספרס. במשחק השלישי בסדרת גמר המערב הוא נפצע בהתנגשות עם שחקן היריבה מאנו ג'ינובילי, ובלעדיו הפסידה דאלאס את הסדרה בתוצאה 2–4.
לפני עונת צירף דון נלסון לסגל דאלאס שני פורוורדים בכירים בדמותם של אנטואן ג'יימיסון ואנטואן ווקר, בעוד שהסנטר הפותח של הקבוצה, ריף לפרנץ, עזב. מאחר שהקבוצה לא הצליחה להחתים סנטר במקומו של לפרנץ הוסט נוביצקי לעמדת הסנטר, כאשר ווקר מתפקד כפאוור פורוורד בעמדתו הטבעית של נוביצקי. על מנת להתמודד עם התפקיד החדש הדורש יותר פיזיות, נוביצקי התמקד באימוניו במשחק ההגנה יותר מאשר בקליעה, וכתוצאה מכך ירדו ממוצעיו העונתיים ל-21.8 נקודות, 8.7 ריבאונדים ו-2.7 אסיסטים למשחק. עם זאת, הוא עדיין היה למוביל של דאלאס בנקודות, בריבאונדים, בחסימות ובחטיפות, נבחר שוב למשחק האולסטאר וכן לחמישיית העונה השלישית. בסיבוב הפלייאוף הראשון פגשה דאלאס פעם נוספת את סקרמנטו קינגס, אך הודחה כבר לאחר חמישה משחקים.
בתור מוביל דאלאס.
בפגרה שלפני עונת עזב את דאלאס סטיב נאש, חברו הקרוב של נוביצקי ואחד מכוכבי הקבוצה לצידו, בעוד שהסנטר אריק דמפיר הצטרף מגולדן סטייט ווריורס. במהלך העונה התפטר מתפקידו מאמן הקבוצה הוותיק דון נלסון ובמקומו מונה לתפקיד אייברי ג'ונסון. על אף עזיבת נאש נוביצקי הצטיין בעונה זו עם שיא חדש לשחקן אירופי של 26.1 נקודות, בנוסף לממוצעים של 9.7 ריבאונדים, 3.1 אסיסטים ו-1.5 חסימות - השניים האחרונים היוו שיאי קריירה בעבורו. בדצמבר 2004 הוא קלע 53 נקודות במשחק מול יוסטון רוקטס, שיא אישי בעבורו, ואף נבחר לראשונה בקריירה לחמישיית העונה הראשונה וסיים שלישי בבחירות ל-MVP של הליגה. במהלך סדרת סיבוב הפלייאוף הראשון, מול יוסטון אשר הובלה על ידי יאו מינג וטרייסי מקגריידי, התקשה נוביצקי מול פורוורד יוסטון ראיין בואן והחטיא זריקות רבות. אף על פי כן, דאלאס ניצחה בתום שבעה משחקים ופגשה את פיניקס סאנס, קבוצתו החדשה של נאש, בחצי גמר המערב. לאחר ארבעה משחקים ניצבו הקבוצות בשוויון 2-2 בסדרה, אך פיניקס ניצחה בשני המשחקים הבאים והדיחה את דאלאס. במשחק השישי, על אף שקלע 28 נקודות, קלע נוביצקי תשע בלבד מ-25 זריקותיו מ, ואף החטיא את כל חמש זריקותיו במהלך ההארכה.
בעונת הפך נוביצקי לשחקן המוביל הבלעדי של דאלאס לאחר שחרורו של מייקל פינלי מהקבוצה, והיה ליחיד שנשאר מ"השלישייה הגדולה" של הקבוצה בתחילת העשור. הוא השיג ממוצעים של 26.6 נקודות, 9 ריבאונדים ו-2.8 אסיסטים למשחק, ושיפר במידה רבה את יכולת הקליעה שלו, כשקלע באחוזים הגבוהים בקריירה שלו מכל הטווחים. בנוסף להשתתפות במשחק האולסטאר המרכזי נוביצקי זכה בתחרות השלשות של הליגה, בה גבר על ריי אלן וגילברט ארינאס. הוא נבחר פעם נוספת לחמישיית העונה הראשונה.
בהובלתו של נוביצקי סיימה דאלאס את העונה עם 60 ניצחונות, הכמות השלישית בגובהה בליגה. במהלך משחקי הפלייאוף ביסס נוביצקי אף יותר את מעמדו כשחקן מוביל בליגה עם ממוצעים גבוהים של 27 נקודות, 11.7 ריבאונדים ו-2.9 אסיסטים למשחק. בסיבוב הראשון ניצחה דאלאס בתוצאה 0–4 את ממפיס גריזליס, ופגשה פעם נוספת את סן אנטוניו ספרס בסיבוב השני. לאחר שוויון 3-3 בתום ששת משחקי הסדרה הראשונים קלע נוביצקי 35 נקודות והוריד 15 ריבאונדים במשחק השביעי, שסייעו לניצחון קבוצתו ולהעפלתה לגמר המערב מול פיניקס. גם נגד פיניקס הצטיין נוביצקי כאשר קלע 50 נקודות במשחק החמישי, והוביל את דאלאס לניצחון בסדרה של שישה משחקים ולהעפלה הראשונה בתולדותיה לסדרת גמר ה-NBA, שם פגשה את מיאמי היט. בסדרת הגמר דאלאס הובילה בתוצאה 0–2, אך מיאמי ניצחה בכל ארבעת המשחקים הבאים בהובלתם של דוויין וייד ושאקיל אוניל. לאחר ההפסד בסדרה קיבל נוביצקי ביקורת על כך שלא היה בשיא יכולתו בסדרה זו.
בעונת הגיע נוביצקי לשיאו במדי דאלאס, כאשר הוביל אותה למאזן של 67 ניצחונות ו-15 הפסדים - החמישי בטיבו בהיסטוריית ה-NBA - שהעניק לה את אליפות העונה הסדירה ואת המקום הראשון בדירוג למשחקי הפלייאוף. הוא השיג ממוצעים של 24.6 נקודות, 8.9 ריבאונדים ו-3.4 אסיסטים למשחק וזכה לראשונה בקריירה שלו בתואר ה-MVP של העונה הסדירה ב-NBA, לאחר שהקדים בבחירות לפרס את סטיב נאש. בכך הפך לאירופי הראשון בתולדות הליגה שזוכה בתואר זה. אף על פי כן, דאלאס הודחה כבר בסיבוב הראשון של משחקי הפלייאוף, על ידי גולדן סטייט ווריורס, והייתה לקבוצה השלישית בהיסטוריה שדורגה ראשונה בעונה הסדירה והודחה על ידי המדורגת שמינית. נוביצקי היה מהסיבות העיקריות להפסד קבוצתו כאשר קלע שמונה נקודות בלבד במשחק השישי שהכריע את הסדרה, ולאורך הסדרה כולה התקשה להתמודד מול ההגנה החזקה שהפעיל סטיבן ג'קסון וקלע ב-38.3 אחוזים בלבד מהשדה.
במהלך עונת הצטרף לדאלאס הרכז הוותיק ג'ייסון קיד, אשר צבר לזכותו הופעות במשחק האולסטאר ונועד להיות מוביל הקבוצה לצד נוביצקי. לאחר שנאבקה במשך מרבית העונה על ההעפלה לפלייאוף מהאזור המערבי החזק במיוחד, סיימה דאלאס במקום השביעי. באותה עונה העמיד נוביצקי ממוצעים של 23.6 נקודות, 8.6 ריבאונדים ו-3.5 אסיסטים למשחק. כמו כן הגיע למספר ציוני דרך בקריירה שלו: הוא השיג לראשונה "טריפל דאבל" כאשר קלע 29 נקודות, הוריד 10 ריבאונדים ומסר 12 אסיסטים במשחק מול מילווקי באקס בפברואר 2008, ובמשחק מול ניו ג'רזי נטס בחודש מרץ עקף את רולנדו בלקמן והפך לקולע המוביל של דאלאס מאבריקס בכל הזמנים. במשחקי הפלייאוף הודחה דאלאס עונה שנייה ברציפות כבר בסיבוב הראשון, לאחר הפסד לניו אורלינס הורנטס בסדרה של חמישה משחקים.
בעונת קלע נוביצקי 25.9 נקודות בממוצע למשחק - הממוצע הרביעי בגובהו בליגה - בנוסף לממוצעים של 8.4 ריבאונדים ו-2.4 אסיסטים. הוא נבחר בפעם הרביעית בקריירה לחמישייה הראשונה של העונה וסייע לדאלאס לסיים במקום השישי במערב, הישג טוב יותר מזה שבעונה הקודמת, עם מאזן של 50 ניצחונות ו-32 הפסדים. בסיבוב הפלייאוף הראשון הוביל נוביצקי את דאלאס לניצחון 1–4 על יריבתה ארוכת-השנים, סן אנטוניו ספרס. בחצי גמר המערב הפסידה הקבוצה 1–4 לדנוור נאגטס, על אף שנוביצקי השיג ממוצעים גבוהים של 34.4 נקודות ו-11.6 ריבאונדים למשחק בסדרה זו.