באפריל 1991, ביקר קנדי בכינוס משפחתי, ולאחר מכן הלך לבר יחד עם בנו ואחיינו. הם חזרו עם נשים, ואחת מהן טענה שקנדי הטריד אותה. השנייה טענה שאחיינו של קנדי אנס אותה. המשטרה חקרה את הנושא, ואנשיו של קנדי התחילו להפיץ מידע שלילי על הנשים. המקרה זכה להתעניינות תקשורתית רבה, והוביל להפצת בדיחות על קנדי. מגזין "טיים" טען שקנדי הוצג כרודף נשים, ואילו ה"ניוזוויק" טען שקנדי הוא הסמל החי לכשלים המשפחתיים.
לאחר בורק, המועמד השנוי ביותר במחלוקת לבית המשפט העליון היה קלרנס תומאס. כשתומאס החל להתראיין בסנאט, לחץ קנדי על תומאס להביע את דעתו בנושא פסק דין רו נגד וייד והפלות. המועמדות נראתה כאילו היא תצלח, אולם לאחר מכן העידה אניטה היל, פרופסור למשפטים, כי תומאס הטריד אותה מינית. המאבק על המועמדות נמשך, אולם קנדי לא יכול היה לדון בנושא בגלל ההאשמות כלפי בנו ואחיינו. קנדי לא אמר הרבה בנושא, וכשכן אמר, נטען שהיה זה מעט מדי ומאוחר מדי.
נטען ששתיקתו של קנדי במהלך הראיונות של תומאס הייתה הרגע הנוראי ביותר בקריירה שלו כסנאטור. הוא נפגע בגלל סגנון חייו. יום לפני ההצבעה בסנאט, נאם קנדי כנגד תומאס ואמר שלתת לו את חמת הספק כמוהו להצהיר שתומאס חשוב יותר מבית המשפט העליון. הוא התנגד למינוי והצביע נגדו. תומאס אושר ברוב דחוק של 52 סנאטורים מול 48, הרוב הדחוק ביותר בו נבחר שופט.
תדמיתו של קנדי נפגעה מאירועים אלה. סקר חשף שרק 22% מהציבור תמכו בו. סקר בבוסטון חשף ש-62% מתושבי מסצ'וסטס מאמינים שעדיף שלא ינסה להיבחר מחדש, שני שלישים האמינו שהוא שיקר למשטרה, וטענו שיפסיד במירוץ לסנאט בהפרש של 25%. ב-17 ביוני 1991, פגש קנדי את ויקטוריה אן רג'י, אם גרושה לשני ילדים, ובתו של חבר ותיק של המשפחה. הם החלו לצאת ובספטמבר היו במערכת יחסים רצינית. בסוף אוקטובר הכיר בביקורת כנגדו בנאום, וטען שהיא קשורה לאכזבה אישית כלפיו. הוא הודה בטעויותיו וטען שיילחם בהן. בדצמבר 1991, נערך המשפט לאחיינו של קנדי. המשפט היה המשפט הנצפה ביותר בטלוויזיה עד למשפטו של או. ג'יי. סימפסון. עדותו של קנדי נחשבה למוצלחת והוכיחה לציבור שלא היה מעורב בפרשה. אחיינו זוכה לבסוף.
קנדי ורג'י המשיכו את מערכת היחסים ביניהם והוא גידל את שני ילדיה. הם התארסו במרץ 1992, ונישאו ביולי 1992 בטקס בביתו של קנדי. הנישואין סייעו לייצוב חייו של קנדי ולשיקום הקריירה שלו.
ללא רצון להיות נשיא, הפך קנדי לחבר טוב של הנשיא ביל קלינטון לאחר שזה נכנס לתפקידו, אף על פי שתמך בסנאטור לשעבר ממסצ'וסטס, פול צונגאס, בבחירות המקדימות. קנדי סייע לקלינטון להעביר את החוק שסייע להקמת אמריקורפס, ותמך בנשיא בנושא הסכם הסחר החופשי של צפון אמריקה. בנושא שהיה חשוב לקנדי מכל, ביטוח הבריאות, הוא תמך אולם לא היה מעורב בתכנון חוק ביטוח הבריאות של 1993, אותו קידמה הגברת הראשונה, הילרי קלינטון. החוק נכשל והחקיקה בנושא נתקעה במשך שנים. ב-1994, המליץ לקלינטון למנות את סטיבן ברייר לבית המשפט העליון. ב-1994 הפך קנדי לסנאטור הראשון בעל עמוד ב-World Wide Web. כך הצליח לבטל את תדמיתו המבוגרת.
בבחירות לסנאט במסצ'וסטס ב-1994, נאלץ קנדי להילחם על כיסאו בפעם הראשונה. הוא התמודד מול מיט רומני, המועמד הצעיר, הכריזמטי והעשיר. רומני הציג את עצמו כיזם מוצלח וכרפורמיסט, עם ערכי משפחה חזקים ועמדה מתונה בנושאים חברתיים, בניגוד לקנדי שהוצג כאיש שלוקה בחסר בתחום. באמצע ספטמבר, הסקרים הראו על שוויון. לקנדי היה חסר כסף, והוא נאלץ לקחת משכנתה שנייה כדי לממן את המירוץ. קנדי הגיב בכמה תשדירי תעמולה שטענו שרומני אינו החלטי ואינו בוס טוב לעובדיו. אשתו החדשה ויקי הייתה נכס למסע הבחירות. קנדי ורומני ערכו עימות טלוויזיוני בסוף אוקטובר שהסתיים ללא מנצח, אולם קנדי התחיל להוביל בסקרים. בבחירות בנובמבר, אף על פי שרוב הדמוקרטים הפסידו את כיסאותיהם, הצליח קנדי להיבחר מחדש ברוב של 58%, המירוץ הצמוד ביותר בקריירה שלו.
בינואר 1995 מתה אמו של קנדי, רוז, בגיל 104. בעקבות מותה החל קנדי להתקרב יותר לדת הקתולית.
סוף שנות התשעים.
תפקידו של קנדי כ"אריה הליברל" בסנאט עמד במבחן ב-1995, לאחר שהרפובליקנים השתלטו על שני בתי הקונגרס וניסו, בהנהגת ניוט גינגריץ', להגשים את סעיפי "האמנה עם אמריקה", המצע הרפובליקני של 1994. דמוקרטים רבים בסנאט ובמדינה הרגישו ייאוש, אולם קנדי החליט להילחם ברפובליקנים. בתחילת 1996, נעצרו הרפובליקנים: רוב סעיפי האמנה לא עברו בסנאט והדמוקרטים, בזכות קנדי, הצליחו להעביר כמה חוקים.
ב-1996, הצליח קנדי להעלות את שכר המינימום הקבוע בחוק. השכר לא עלה שוב עד ל-2006. לאחר כישלון קלינטון בנושא ביטוח הבריאות, ביקש קנדי להגדיל את הכנסות המדינה. קנדי עבד עם ננסי קאסבאום, סנאטורית רפובליקנית, כדי להעביר ב-1996 את "HIPAA", חוק שיאפשר נגישות רחבה יותר לביטוחי הבריאות. בנוסף, אילץ את חברות הביטוח להתייחס בשוויון למטופלים עם מחלות נפש. ב-1997, העביר קנדי חוק ביטוח בריאות לילדים, שהשתמש במיסים מטבק כדי לממן הרחבה של ביטוח בריאות לילדים.
קנדי תמך בנשיא קלינטון במהלך פרשת מוניקה לווינסקי, וניסה לתמוך בו מבחינה משפטית. במשפט ההדחה של קלינטון, תמך קנדי בזיכוי קלינטון, וטען שהרפובליקנים פגעו בחוקה בניסיונם להדיח את קלינטון.
ב-16 ביולי 1999, שוב ספגה משפחת קנדי אובדן: מטוסו של ג'ון קנדי ג'וניור התרסק אל האוקיינוס האטלנטי, והוא נהרג יחד עם אשתו וגיסתו. טד, כאח הבוגר היחיד במשפחה, ניחם את משפחתו המורחבת יחד עם הנשיא קלינטון. הוא טען שכאביו, לג'ון קנדי היו את כל הזכויות פרט לאריכות ימים. טד נאלץ לגדל את כל שאר בני המשפחה. רבים הופתעו מכך שטדי, שנחשב לאח הקטן והמרדן, הפך לאב המשפחה.
שנות האלפיים.
לקנדי היה קל להיבחר מחדש לסנאט בשנת אלפיים. קנדי זכה ל-73% מהקולות. במהלך המאבק המשפטי על תוצאות הבחירות הנשיאותיות בפלורידה, תמך קנדי בסגן הנשיא אל גור. לאחר מערכת הבחירות, סירבו דמוקרטים רבים לשתף פעולה עם הנשיא ג'ורג' ווקר בוש. קנדי, לעומתם, ראה בבוש אדם שמתעניין בנושא החינוך, ובוש ראה בקנדי בעל ברית בסנאט. קנדי הסכים לקבל כמה הגבלות מצד הנשיא בתמורה להוספת תקציבים למערכת החינוך. לאחר מכן קידם בוש את הרפורמה המרכזית שלו בתחום החינוך (No Child Left Behind Act), שהייתה פרי הבטחתו בבחירות שנערכו כשנה קודם לכן. מטרת הרפורמה הייתה לצמצם את פערי החינוך בין עניים לעשירים ולהגדיל את ההשקעה הלאומית בחינוך. במסגרת הרפורמה הורחב המימון של מערכת החינוך, ובתי ספר שבהם למדו ילדים להורים שנמצאים בעשירוני ההכנסה הנמוכים, אמורים היו לזכות בתקציב ציבורי גבוה יותר. החוק עבר במאי וביוני 2001 ובוש חתם עליו בינואר 2002. ב-2003 התחרט קנדי על תמיכתו בחוק, בטענה שיש להקציב עוד תשעה מיליארד דולרים למערכת החינוך. הוא טען שהרפורמה נחוצה, אולם אין לה מימון, והאשים את בוש בכך שחזר בו מהבטחתו. הדמוקרטים טענו שפשרנותו של קנדי גברה עליו. הבית הלבן טען שהתקציבים נפגעו בשל המלחמות שניהל ממשל בוש במזרח התיכון.
קנדי היה בסנאט, בפגישה עם לורה בוש במהלך פיגועי 11 בספטמבר. שניים מהמטוסים המריאו מבוסטון, ובשבועות לאחר מכן טלפן קנדי לכל אחת מהמשפחות במסצ'וסטס שאיבדו את יקיריהם בפיגועים. הוא העביר חקיקה שסיפקה הטבות וביטוח בריאות למשפחות השכולות, וניסה להשפיע על קרן הפיצויים של קרבנות הפיגועים. קנדי שמר על קשר עם המשפחות גם לאחר שנים.
בתגובה לפיגועים, תמך קנדי בהדחה האמריקנית של משטר הטליבאן באפגניסטן. קנדי התנגד למלחמת עיראק מתחילתה והיה בין עשרים ושלושה סנאטורים שהצביעו נגד ההחלטה לפלוש לעיראק באוקטובר 2002. עם התגברות ההתנגדות בעיראק לצבא האמריקני, טען קנדי שהמלחמה היא "וייטנאם של בוש". קנדי תמך בתקצוב רכבי HMMWV להגנה על החיילים.
למרות מערכת היחסים הקשה בין קנדי ובוש בנושאי ההשקעות בחינוך, השניים עבדו ביחד על הרחבת תוכנית מדיקר לכיסוי הוצאות על תרופות. הדמוקרטים שוב פקפקו בקנדי, אולם הוא טען שאין להחמיץ את התוספת של 400 מיליארד דולר למערכת הבריאות. לבסוף החליט קנדי להתנגד לגרסה הסופית של החוק מפני שטען שהוא מסייע לחברות הפרטיות. החוק עבר בסוף 2003, ושוב טען קנדי שממשל בוש בגד בו.
בבחירות המקדימות במפלגה הדמוקרטית ב-2004, תמך קנדי בחברו לסנאט ממצס'וסטס, ג'ון קרי. קנדי משך את הפועלים והמיעוטים, וסייע לקרי להיבחר.
בוש נבחר מחדש, וקנדי המשיך להתנגד לו. עם זאת, החליט קנדי לשתף פעולה עם הרפובליקנים בנושא רפורמה בהגירה. קנדי ניהל את הוועדה בנושא ביטחון גבולות, וב-2005, יחד עם הסנאטור ג'ון מקיין, יצר מתווה לחקיקה בנושאי הגירה. ב-2007 ניסה קנדי לחוקק עוד חוק לרפורמה בהגירה, וזכה לתמיכת הממשל. החוק זכה להתנגדות עזה, ולמרות ניסיונו של קנדי, החוק לא עבר. קנדי טען שינסה להמשיך להעביר את החוק.
ב-2006 הוציא קנדי ספר ילדים שסיפר על כלבו. בנוסף פרסם אוטוביוגרפיה פוליטית.
ב-2006, המטוס בו טס נפגע מברק ונאלצו לפנותו משם.
גם ב-2006 נבחר קנדי שוב לסנאט, עם 69% מהקולות.
יחסיו עם ברק אובמה והתדרדרות במצב הבריאותי של קנדי.