הנאגטס נקטו בצעד חיובי לבנייתה מחדש של הקבוצה אחרי שבחרו את הסנטר של אוניברסיטת ג'ורג'טאון דיקמבה מוטומבו, בבחירה העשירית של דראפט 1991. מוטומבו העביר עונת רוקי מוצלחת, כשהוא מסיים שני אחרי לארי ג'ונסון בהצבעות לבחירת רוקי השנה. הנאגטס סיימו את העונה במאזן שלילי 24–58 באותה העונה. לקראת עונת פיטרו הנאגטס את וסטהד והחתימו במקומו את כוכב העבר דן איסל. בדראפט של אותה שנה בחרו הנאגטס בבחירה החמישית את הפורוורד האתלטי לפונזו אליס, בעזרתו שיפרו הנאגטס את מאזנם ל-36–46 אך החמיצו במעט את הפלייאוף.
בעונת החליפה הנהלת הנאגטס את צבעי המועדון לכחול כהה, זהב מטאלי ואדום יין. בהובלתו של מוטומבו, אליס ומחמוד עבדול-ראוף (ששינה את שמו מכריס ג'קסון שנה אחת קודם לכן), הצליחו הנאגטס לסיים את העונה במאזן חיובי, 42–40, לראשונה מאז ימיו של דאג מו. הנאגטס תפסו את המקום השמיני בפלייאוף אזור המערב, והתמודדו מול המדורגת ראשונה סיאטל סופרסוניקס. הנאגטס נחשבו לאנדרדוג מובהק בהתמודדות, כשרק מעט משחקני הסגל היו בעלי ניסיון פלייאוף. לאחר שהפסידו בשני המשחקים הראשונים בסיאטל, הגיעה הסדרה לדנוור. הנאגטס הצליחו לנצח בשני המשחקים הבאים בסדרה והשוו את הסדרה, לקראת המשחק החמישי והמכריע. במשחק החמישי הצליחו הנאגטס לעשות היסטוריה, כשהם גוברים על הסופרסוניקס בתוצאה 98–94. בכך הפכו הנאגטס לקבוצה הראשונה בתולדות פלייאוף ה-NBA שמדיחה את הקבוצה המדורגת ראשונה בשלב הפלייאוף הראשון. בסיבוב השני כמעט הצליחה דנוור לחולל הפתעה נוספת, אך בסופו של דבר הם נוצחו על ידי יוטה ג'אז במשחק השביעי והמכריע.
בשנת 1994 רכשו הנאגטס את הקלע של הסופרסוניקס דייל אליס, ובחרו בדראפט את שחקנה של אוניברסיטת מישיגן ג'יילן רוז. הנאגטס נאבקו בעונת כשהם גורמים למאמן איסל להתפטר מתפקידו באמצע העונה. עוזר המאמן, ג'ין ליטל, קיבל עליו את התפקיד למשך תקופה קצרה עד שהחזיר את המפתחות לג'נרל מנג'ר ברני ביקרסטאף. הנאגטס הצליחו להתאושש ולהתברג במקום השמיני בפלייאוף, כשהם מסיימים את העונה במאזן 41–41, אך הם נוצחו בסוויפ על ידי סן אנטוניו ספרס בסיבוב הראשון של הפלייאוף.
בדראפט 1995 בחרו הנאגטס עם הבחירה השנייה את אנטוניו מקדייס אשר הפך ל"פנים" של המועדון בשנים הבאות, בעוד מוטומבו עזב לאטלנטה הוקס, עבדול-ראוף הועבר בטרייד לסקרמנטו קינגס, ואליס החמיץ את רוב העונות הבאות עקב פציעות חוזרות ברגליו. הנאגטס התקרבו לשבירת שיאים שליליים בעונת , כשניצחו 11 משחקים בלבד לאורך העונה הסדירה. במהלך העונה רשמה הקבוצה את רצף ההפסדים השני באורכו בתולדות הליגה - 23 הפסדים רצופים.
קשיים במכירת המועדון (1995–2003).
הקבוצה השתרכה בתחתית הליגה בסוף שנות ה-90, ואת קשייה של הקבוצה ניתן לתלות חלקית בחוסר יציבות בבעלות על המועדון. בשנת 1995 קנתה חברת קומסאט את קבוצת ההוקי קוויבק נורדיקס והעבירה אותה מהעיר קוויבק שבקנדה לדנוור תחת השם קולורדו אוולאנש. גיוון עסקיה של החברה לתחום ספורט התברר כנטל - החריגה הגבוהה בעלויות הבניה של האולם החדש, פפסי סנטר, הביאו לחוסר שביעות רצון בקרב בעלי המניות בחברה. לבסוף, בשנת 1997, הסכימה קומסאט עקרונית למכור את מטריית פעילויות הספורט שלה לחברת ליברטי מדיה, אך ליברטי לא הייתה מעוניינת בבעלות על קבוצות ספורט מקצועני באותה עת. בסופו של דבר, בשנת 1999, מכרה אסנט אנטרטיינמנט (חברת הגג המנהלת את השקעות הספורט של קומסאט) את דנוור נאגטס ואת קולורדו אוולאנש לאיל ההון דונלד סטרם עבור 461 מיליון דולר.
בעיה חדשה התעוררה כאשר העיר דנוור סירבה להעביר את חלקת האדמה עליה עמד אולם הפפסי סנטר לידי המועדון, אלא אם כן סטורם יתחייב להשאיר את המועדונים בעיר דנוור ב-25 השנים הקרובות. סטורם הציע את הצעת הרכישה בעבור מועדוני הספורט בשמו הפרטי ולא תחת שם עסקיו, והעיר רצתה לבטח את עצמה למקרה וסטורם יחלוף מהעולם או ימכור את המועדון לפני תום 25 השנים. בעוד סטורם היה מוכן לתת לעיר התחייבות ארוכת שנים, הוא לא היה מכון לקחת אחריות למקרה והוא ימות או ימכור את המועדון. לאחר שהמשא ומתן התמוטט קנתה ליברטי את כל חברת אסנט, אך השאירה את הנאגסט ואת האוולנש למכירה בשוק. בינתיים, חזר איסל לתפקיד המאמן הראשי בשנת 1999, אך המשא ומתן המתארך בנוגע לבעלות על המועדון מנעה ממנו את האפשרות לבנות מחדש את הקבוצה. מעט לפני תחילת עונת אמר איסל לעיתונים כי ישנן מספר החלטות אותן הוא לא יכול לבצע עקב המצב בו הבעלות על המועדון אינה מוכרעת.
לבסוף, במהלך חודש יולי 2000, נרכשו קולורדו אוולאנש, דנוור נאגטס ואולם הפפסי סנטר על ידי יזם הנדל"ן סטאן קרונקי תמורת 450 מיליון דולר. במסגרת העסקה סוכם כי חברת ליברטי תשאיר בידה 6.5% מהאחזקות במועדוני הספורט, וכן כי קרונקי יעביר את המועדונים לידי חברת נאמנות שתבטיח את הישארותם של מועדוני הספורט בעיר דנוור לפחות עד לשנת 2025. לאחר העסקה איגד קרונקי את עסקי הספורט שלו תחת חברת "קרונקי ספורט אנטרפרייז".
תקופת כרמלו אנתוני וג'ורג' קארל (2003–2013).
2003–2006.
לקראת עונת הציגה הקבוצה סמל ומדים חדשים, ובחרו בדראפט 2003 את כרמלו אנתוני בבחירה השלישית. בתוך חודשיים מפתיחת העונה צברו הנאגטס יותר ניצחונות (19) מאשר בכל העונה הקודמת, ובסיום העונה העפילו לשלב הפלייאוף לראשונה מזה 9 עונות. בפלייאוף עצמו הודחה דנוור בסיבוב הראשון, לאחר שהפסידה למינסוטה טימברוולבס בתוצאה 4–1. סיבה עיקרית למהפך שהתחולל בקבוצה ניתן לזקוף למהלכיו של קיקי ואנדוויי, שחקנה לשעבר של הנאגטס, שנטל על עצמו את תפקיד הג'נרל מנג'ר של המועדון ב-9 באוגוסט 2001.
ב-28 בדצמבר 2004, פיטרו הנאגטס את מאמנם ג'ף בנזדליק ומינו במקומו, באופן זמני, את כוכבה לשעבר של לוס אנג'לס לייקרס, מייקל קופר. מאוחר יותר מינו הנאגטס את ג'ורג' קארל, אשר הוביל את הקבוצה למאזן חיובי של 32–8 בחציה השני של העונה, שהבטיח את מקומה של הקבוצה בפלייאוף שנה שנייה ברציפות. בסיבוב הפלייאוף הראשון לא הצליחו הנאגטס לעבור את סן אנטוניו ספרס, לאחר שנצחו את המשחק הראשון בסן אנטוניו אך הפסידו בארבעת המשחקים הבאים ואת הסדרה כולה 1–4.
בעונת , הצליחו הנאגטס לזכות באליפות הבית הצפון-מערבי, לראשונה מזה 18 שנים. הישג זה הציב את הקבוצה במקום השלישי באזור המערבי. הנאגטס פגשו את לוס אנג'לס קליפרס, שלמרות מיקומם השישי בדירוג המערב החזיקו במאזן יותר טוב מאשר הנאגטס בסיומה של העונה הסדירה, וכתוצאה מכך זכו הקליפרס ביתרון הביתיות. הקליפרס גברו על הנאגטס בחמישה משחקים. זמן קצר לאחר מכן, הודיעה הנהלת המועדון כי חוזהו של הג'נרל מנג'ר קיקי ואנדוויי לא יחודש, והוא הוחלף בידי מארק וורקנטין.
ב-18 בדצמבר 2006 הושעו כרמלו אנתוני, ג'יי. אר. סמית' וננה (ל-10, 15 ומשחק בודד, בהתאמה) עקב תגרה שהתרחשה בשתי הדקות האחרונות של המשחק נגד הניו יורק ניקס יומיים קודם לכן. התגרה ניצתה עקב עבירה קשה אותה ביצע שחקן הניו יורק ניקס, מארדי קולינס, על ג'יי. אר. סמית' שהיה בדרכו לסל. לפי כרמלו אנתוני הזהירו מאמן הניקס אייזיאה תומאס לא להתקרב לרחבת הצבע זמן קצר לפני העבירה הקשה.
2006–2008: אנתוני ואייברסון.
ב-19 בדצמבר 2006, ביצעו הנאגטס טרייד אשר שלח את ג'ו סמית', אנדרה מילר ושתי בחירות סיבוב ראשון בדראפט 2007 לפילדלפיה 76' בתמורה לכוכב הסיקסרס אלן אייברסון (יחד עם אייבן מקפרלין שנופה מידית מסגל הנאגטס). המהלך נתן לנאגטס את שני הסקוררים המובילים של הליגה באותו הזמן – אייברסון ואנתוני – שכל אחד מהם קלע יותר מ-30 נקודות בממוצע למשחק בעת ביצוע הטרייד. עם צירופו של אייברסון רבים החשיבו את הנאגטס לאחת מקבוצות עלית המערב, לצד דאלאס מאבריקס, פיניקס סאנס וסן אנטוניו ספרס, אך הקבוצה הציגה יכולת מאכזבת וסיימה את העונה במקום השישי במערב, שהפגיש אותה בסיבוב הראשון של הפלייאוף מול סן אנטוניו ספרס. בפלייאוף, הנאגטס ניצחו את המשחק הראשון בסדרה, ולמעשה "גנבו" את יתרון הביתיות מהספרס, אך במה שנראה כשידור חוזר של פלייאוף 2005, הספרס התאוששו וניצחו ארבעה משחקים ברציפות שהובילו להדחה של הנאגטס. הייתה זו השנה הרביעית ברציפות שהנאגטס מודחים מהפלייאוף בסיבוב הראשון.
את עונת סיימו הנאגטס עם 50 ניצחונות בדיוק, כשבמחצית העונה מאזנם היה 25–16 (ובסופה של העונה הסדירה הם הגיעו ל-50–26 מאזן השלישי בטיבו בהיסטוריה של המועדון מאז הצטרפותם לליגת ה-NBA בשנת 1976). לקראת סיום העונה, ב-16 במרץ 2008, קלעו הנאגטס 168 נקודות בניצחון 168–116 על סיאטל סופרסוניקס, אשר היה המשחק השלישי בסך הנקודות למשחק בודד בעונה הסדירה בהיסטוריה של ה-NBA. הייתה זו העונה הראשונה מאז עונת בה הנאגטס מסיימים את העונה הסדירה עם לפחות 50 ניצחונות. דנוור סיימה את העונה כמדורגת שמינית באזור המערב לפלייאוף 2008, ו-50 הניצחונות אותם השיגו היו שיא לקבוצה המדורגת במקום השמיני במערב מאז הורחב פלייאוף ה-NBA ל-16 קבוצות בעונת . בסיבוב הראשון של הפלייאוף גברה לוס אנג'לס לייקרס על הנאגטס בסוויפ, ובכך הודחה דנוור בסיבוב הראשון בפעם החמישית ברציפות.
2008–2011: אנתוני ובילאפס.
ב-16 ביולי, לקראת עונת , העבירו הנאגטס את שחקן ההגנה של העונה מרכוס קמבי ללוס אנג'לס קליפרס, תמורת בחירת סיבוב שני בדראפט. אחת הסיבות לטרייד המוטה הייתה ניסיון להפחית את החריגה מתקרת השכר של הנאגטס. ב-3 בנובמבר 2008, שלושה משחקים בתוך העונה, הועבר אלן אייברסון בטרייד לדטרויט פיסטונס תמורת צ'ונסי בילאפס, אנטוניו מקדייס, וצ'ק סאמב (מקדייס וסאמב נופו מהקבוצה תוך זמן קצר).