בפלייאוף של אותה עונה שיחקו הניקס ב-25 משחקים, שיא NBA שישבר רק ב-2008 על ידי בוסטון סלטיקס. בסיבוב הראשון הניקס הדיחו את ניו ג'רזי נטס. בחצי גמר המזרח הניקס שיחקו נגד הבולס, ולאחר שלוש שנים שהבולס ניצחו היה תורם של הניקס לעשות זאת, בסדרה בת 7 משחקים. בגמר המזרח הניקס שיחקו נגד אינדיאנה פייסרס. בזכות הופעותיו המצוינות של כוכב אינדיאנה, רג'י מילר, הפייסרס הובילו בסדרה 2–3. הניקס ניצחו בשני המשחקים הבאים ועלו לגמר NBA ראשון מאז 1973. בגמר ה-NBA הניקס שיחקו נגד יוסטון רוקטס. שני המשחקים הראשונים שוחקו במגרשה של יוסטון רוקטס והתוצאה הייתה 1-1, שלושת המשחקים הבאים שוחקו במדיסון סקוור גארדן כאשר יוסטון רוקטס ניצחו גם במשחק השלישי, והניקס ניצחו בשני המשחקים הבאים ועלו ליתרון 3–2 בסדרה, כשרק ניצחון אחד מפריד בינם לבין זכייה באליפות. הרוקטס ניצחו במשחק השישי, וכפו משחק שביעי ומכריע. במשחק האחרון הניקס הפסידו 84–90, כשהמאפיין הבולט של המשחק היה ערב הקליעה הנוראי של סטארקס, אשר קלע רק 2 מתוך 18 זריקות מהשדה, כולל 0 מ-11 מהשלוש.
בעונה הבאה הניקס השיגו מאזן 27–55 וסיימו במקום השני בבית האטלנטי. אחרי שהדיחו את קליבלנד קאבלירס בסיבוב הראשון של הפלייאוף הם נפגשו עם אינדיאנה פייסרס בחצי גמר המזרח. במשחק הראשון כוכב הפייסרס רג'י מילר קלע 8 נקודות ב-8 השניות האחרונות, והכריע את המשחק לטובת קבוצתו, 107-105. הסדרה הגיעה למשחק שביעי, ובמשחק השביעי לפטריק יואינג הייתה הזדמנות לקבוע הארכה עם הבאזר, אך הוא החטיא ליי-אפ והניקס הפסידו 95–97. ריילי התפטר יום לאחר מכן ובמקומו מינו הניקס את דון נלסון.
הגעתו של נלסון שינתה את סגנון המשחק של הניקס מהגנתי להתקפי, אך אחרי 59 משחקים בלבד בעונת 1995/1996 הוא פוטר. במקומו הניקס לא חיפשו להחתים מאמן ידוע ובעל קבלות, ובמקום זאת הם החתימו את ג'ף ואן גנדי חסר הניסיון, שלא היה בעמדת המאמן הראשי לפני כן. הניקס השיגו מאזן של 35–47, והם עלו לפלייאוף. בסיבוב הראשון הם הדיחו את קליבלנד קאבלירס בסוויפ. בחצי גמר המזרח הניקס הודחו על ידי שיקגו בולס שחזרו להיות דומיננטיים עם חזרתו של מייקל ג'ורדן בסדרה בת 5 משחקים. הבולס חוו את העונה הטובה בהיסטוריה של ה-NBA, עם 72 ניצחונות וזכייה באליפות.
בתחילת עונת 1996/1997 צירפו הניקס את לארי ג'ונסון ואלן יוסטון. ביחד עם התוספות המשמעותיות האלו הם השיגו מאזן 25–57. בסיבוב הראשון הניקס הדיחו בסוויפ את שארלוט הורנטס. בחצי גמר המזרח הם פגשו את מיאמי היט שאומנה על ידי פט ריילי, שהתפטר מהניקס לפני מספר שנים. בארבעת המשחקים הראשונים הניקס הובילו 1–3. במשחק החמישי התרחשה קטטה שגרמה להרחקתם של מספר שחקני מפתח. כשיואינג ויוסטון הורחקו מהמשחק השישי, וג'ונסון וסטארקס הורחקו מהמשחק השביעי הניקס הפסידו בסדרה.
עונת 1997/1998 אופיינה בעיקר בחסרונו של פטריק יואינג שנפצע ב-22 בדצמבר ולא חזר לשחק לא בעונה ולא בפלייאוף. הניקס השיגו מאזן 39–43, שסידר להם מקום בפלייאוף. בסיבוב הראשון הם הדיחו את מיאמי היט, ובחצי הגמר הם נפגשו עם אינדיאנה פייסרס. הניקס הפסידו לפייסרס בסדרה בת 5 משחקים, למרות חזרתו של יואינג למגרשים במשחק השני. זו הייתה השנה הרביעית ברציפות שהניקס הודחו בחצי גמר המזרח.
עונת 1998/1999 הייתה מקוצרת בשל שביתת השחקנים. לפני תחילתה הניקס העבירו את סטארקס בטרייד בתמורה ללטרל ספריוול, וצ'ארלס אוקלי הועבר לטורונטו ראפטורס בתמורה למרכוס קמבי. אחרי שבקושי הגיעו לפלייאוף עם מאזן 23–27, הניקס התחילו בסיפור ה"סינדרלה" שלהם. בסיבוב הראשון הניקס הדיחו את מיאמי היט שסיימו את העונה במקום הראשון במזרח. מקרה זה היה השני בהיסטוריה של ה-NBA שהמדורגת השמינית מדיחה את הראשונה, והמקרה הראשון והיחידי באזור המזרחי.
אחרי שהניקס הדיחו את אטלנטה הוקס בחצי גמר המזרח בסוויפ הם פגשו את אינדיאנה פייסרס בגמר המזרח. אף על פי שיואינג סבל מפציעה החל מהמשחק השלישי הניקס ניצחו את הפייסרס, והפכו לקבוצה הראשונה בהיסטוריה של ה-NBA שעלו לגמר מהמקום השמיני. למרות ההישג הניקס שחסרו את יואינג פגשו את סן אנטוניו ספרס שכללה את האולסטארים דייוויד רובינסון וטים דאנקן, והם הפסידו ב-5 משחקים.
עונת 1999/2000 הפכה לעונה האחרונה שבה השתתף פטריק יואינג, והייתה למעשה סיומה של תקופה בניקס. הניקס הגיעו למאזן 30–52 בעונה זו, ועלו לפלייאוף. בסיבוב הראשון הם הדיחו את מיאמי היט בעוד סדרה מותחת, שהסתיימה אחרי 7 משחקים כשבשביעי יואינג הטביע דאנק ניצחון. הניקס הפסידו בגמר המזרח לאינדיאנה פייסרס בסדרה בת 6 משחקים. לאחר סיום העונה הם שלחו את יואינג בטרייד לסיאטל סופרסוניקס, וכך בעצם הסתיים עידן יואינג - עם הרבה עליות לפלייאוף, שתי הופעות בגמר וללא אליפות.
2000–2010: הצניחה שלאחר עידן יואינג.
בעונת 2000/2001, העונה הראשונה המילניום החדש, הניקס השיגו מאזן טוב של 34–48 למרות עזיבתו של יואינג. למרות ההצלחה היחסית בעונה הסדירה, בסיבוב הראשון של הפלייאוף הניקס הפסידו בחמישה משחקים לטורונטו ראפטורס. את עונת 2001/2002 הניקס התחילו במאזן 9–10, מה שגרם לג'ף ואן גנדי להתפטר ב-8 בדצמבר 2001 (כשסיבתו הרשמית היא לפנות זמן להיות עם משפחתו). הניקס מינו את עוזר המאמן דון צ'ייני לעמדת המאמן, וסיימו את העונה עם מאזן 30–52. זו הייתה הפעם הראשונה מאז עונת 1986/1987 שהניקס לא העפילו לפלייאוף.
במשך אותה עונה הניקס ניסו להתחזק, כשהשתמשו במספר טריידים. הם הביאו את שאנון אנדרסון והאוורד איסלי, אשר לשניהם יש משכורת גבוהה וחוזה להרבה שנים. אוהדי הניקס והרבה פרשנים לא אהבו את המהלכים האלו, מפני שאיסלי ואנדרסון לא תרמו לקבוצה כמו גובה המשכורת שלהם, שבינתיים לא מאפשרת לניקס לקנות שחקנים חדשים. בעונת 2002/2003 היה שיפור קל בקבוצה, והם הגיעו למאזן 37–45. למרות השיפור הם לא העפילו לפלייאוף שנה שנייה ברציפות.
בתחילת עונת 2003/2004 המאזן של הניקס היה 15–24, מה שגרם לראשי הקבוצה לחשוב על זעזועים. ב-22 בדצמבר 2003 מונה שחקן העבר של הדטרויט פיסטונס וסגן נשיא טורונטו רפטורס, אייזיאה תומאס לנשיאה של הקבוצה. תומאס החליף את מאמן הניקס בלני וילקינס. הטרייד הראשון שתומאס ביצע הביא לניקס את האולסטאר סטפון מרבורי, שמשחק בעמדת הרכז. המורל של הקבוצה עלה עוד יותר כשהם צירפו את קית' ואן הורן ומייקל דוליק. ואן הורן הועבר מאוחר יותר למילווקי באקס בתמורה לטים תומאס ונאזי מוחמד. הניקס עלו לפלייאוף עם מאזן 39–43, אבל הודחו בסוויפ בסיבוב הראשון בידי הניו ג'רזי נטס.
במשך עונת 2004/2005 המאמן ווילקינס התפטר, ובמקומו מונה הרב ויליאמס. הניקס סיימו את העונה עם מאזן 33–49, ולא עלו לפלייאוף. אחרי סיומה של העונה הניקס החתימו את לארי בראון, שיהיה בעמדת המאמן. בראון קיבל חוזה גדול לחמש שנים ששוויו 50 מיליון $, כשהניקס מקווים שהוא יוביל אותם לפלייאוף.
לפני העונה הבאה הניקס החתימו שני סנטרים. הראשון, ג'רום ג'יימס, והשני הוא אדי קרי אותו הם רכשו משיקגו בולס. קרי הגיע ביחד עם אנטוניו דייוויס, והבולס קיבלו בתמורה את תומאס ומייקל סוויטני. למרות ההגעות של השחקנים החדשים והמאמן הניקס "השיגו" מאזן 23–59, המאזן הלפני אחרון בליגה רק אחרי פורטלנד טרייל בלייזרס. בראון פוטר בסיומה של העונה.
בשנתיים האחרונות בוצעו הרבה טריידים ומהלכים של אייזיאה תומאס שגרמו לאי הסכמה מצד האוהדים והפרשנים. ראשית, הבאת הרבה שחקנים יקרים במיוחד כמו מרבורי, ג'מאל קרופורד, ג'יימס, מאליק רוז, ג'יילן רוז וסטיב פרנסיס. שנית הוא קיבל שחקנים שלא תרמו לו הרבה כמו פני הארדוויי, ג'רום ויליאמס ומוריס טיילור בתמורה לבחירות דראפט. למרות זאת ההחלטות של תומאס בדראפט עצמו נחשבו לטובות כשהוא בחר בשחקנים כמו דייוויד לי, טרבור אריזה, נייט רובינסון ו-וילסון צ'נדלר.
בעונת 2006/2007 שיפרו הניקס את מאזנם ב-10 ניצחונות, כשהשיגו מאזן 33–49. בערב דראפט 2007 שלח תומאס את צ'אנינג פריי ואת פרנסיס לפורטלנד טרייל בלייזרס בתמורה לזאק רנדולף דן דיקאו ופרד ג'ונס. דיקאו הועבר מעט מאוחר יותר ללוס אנג'לס קליפרס בתמורה לג'ארד ג'ורדן. הניקס החלו את עונת 2007/2008 במאזן 1–9, וסיימו אותה במאזן 23–59, השוואת השיא השלילי של המועדון. ב-29 בנובמבר 2007 הניקס הפסידו את הפסדם הגדול ביותר בהיסטוריה של המועדון והשלישי בהיסטוריה של ה-NBA, 104-59 לבוסטון סלטיקס.
ב-2 באפריל 2008 פוטר תומאס ובמקומו מונה דוני וולש. ב-13 במאי באותה שנה וולש מינה את המאמן לשעבר של פיניקס סאנס, מייק ד'אנטוני לעמדת המאמן. שבוע לאחר מכן הניקס בחרו בדראפט 2008 את דנילו גלינארי האיטלקי בבחירה ה-6. הניקס החתימו גם את הרכז כריס דוהון. ב-21 בנובמבר הניקס שלחו את ג'מאל קרופורד לגולדן סטייט ווריורס בתמורה לאל הרינגטון. מעט מאוחר יותר הם העבירו את זאק רנדולף ומרדי קולינס ללוס אנג'לס קליפרס בתמורה לקטינו מובלי וטים תומאס. מטרתם של הניקס הייתה לחסוך בשכר שחקניה העכשוויים כדי לשחרר הרבה כסף לקנייה עתידית של אחד מהאולסטארים לברון ג'יימס, דוויין וייד, כריס בוש או אמארה סטודמאייר שישתחררו מחוזיהם ב-2010. ב-2009 הניקס העבירו את תומאס ג'יימס ואנתוני רוברסון לשיקגו בולס בתמורה ללארי יוז. בנוסף הם שלחו את מאליק רוז לאוקלהומה סיטי ת'אנדר וקיבלו את כריס וילקוקס. מרבורי סיים את חוזהו בניקס באותה שנה. באותה שנה לי השיג 65 פעמים דאבל דאבל, אך הניקס שיפרו את מאזנם רק ב-9 משחקים.