באופן ברור הלייקרס נראו כמועמדים לאליפות נוספת, השנייה ברציפות, בעונה הבאה, , אך הפעם נתקלו הלייקרס בקשיים רבים יותר, כאשר כבר לפני פגרת האולסטאר (המסמנת את מחצית העונה) צברו הלייקרס 16 הפסדים, אחד יותר ממה שצברו בעונה הקודמת כולה. למרות זאת, הצליחו הלייקרס לחזור לעצמם ולגבור על סקרמנטו קינגס במירוץ לתואר האליפות של הבית הפאסיפי, כשסיימו את העונה הסדירה במאזן 56:26, עם ניצחון אחד יותר מאשר לקינגס. בפלייאוף, דהרו הלייקרס לגמר ה-NBA כאשר ניצחו בשלוש סדרות הפלייאוף הראשונות בסוויפ על פורטלנד טרייל בלייזרס, סקרמנטו קינגס וסן אנטוניו ספרס (בהתאמה). סדרת גמר המערב מול הספרס הייתה אחת החד צדדיות בהיסטוריה של ה-NBA כאשר הלייקרס מנצחים בהפרש ממוצע של 22 נקודות. בגמר ה-NBA פגשו הלייקרס את פילדלפיה 76' בהנהגתו של אלן אייברסון, הלייקרס הפסידו במשחק הראשון בסדרה, אך השתלטו על המשכה כשגברו על פילדלפיה בארבעת המשחקים הבאים בדרך לניצחון 4:1 וזכייה ה-13 באליפות ה-NBA בהיסטוריה של המועדון. שאקיל אוניל נבחר בפעם השנייה ברציפות ל-MVP של סדרת הגמר, ודרק פישר קבע שיא NBA עם 15 סלי 3 נקודות במהלך סדרת גמר המערב מול סן אנטוניו ספרס. הלייקרס סיימו את פלייאוף 2001 במאזן 15:1, מאזן הפלייאוף הטוב ביותר לעונה בודדת בהיסטוריה של ה-NBA.
הלייקרס החלו בצורה חזקה את עונת , כשהם מנצחים 16 מ-17 המשחקים הראשונים של העונה. אך, פציעה טורדנית בבוהן כף הרגל הטרידה את שאקיל אוניל לאורך העונה והלייקרס איבדו את אליפות הבית הפאסיפי לסקרמנטו קינגס, כשהלייקרס סיימו את העונה הסדירה במאזן 58:24, שהספיק למקום השלישי במערב. בפלייאוף, הלייקרס דילגו בקלות על שני הסיבובים הראשונים, כאשר הם גוברים על פורטלנד טרייל בלייזרס בסוויפ, 4:0, בסיבוב הראשון ועל סן אנטוניו ספרס בחצי גמר המערב בחמישה משחקים, 4:1. בגמר המערב פגשו הלייקרס את סקרמנטו קינגס המוכשרים, שרבים החשיבו אותה כקבוצה המסוגלת לעבר את המשוכה בדמות הלייקרס ולהגיע לגמר ה-NBA. הסדרה, שנחשבת לאחת המרתקות בהיסטוריה של סדרות הגמר האזוריות בהיסטוריה של ה-NBA, הייתה צמודה לכל אורכה. הקינגס היו במרחק של שניות בודדות לעלות ליתרון של 3:1 לאחר המשחק הרביעי בלוס אנג'לס, אך סל שלוש נקודות של רוברט הורי עם הבאזר, השווה את תוצאת הסדרה ל-2:2, ואיפשר ללייקרס לדחוף את הסדרה למשחק השביעי והמכריע שנערך בסקרמנטו. המשחק השביעי התברר כדרמטי כקודמיו בסדרה, אך בסופו של דבר הצליחו הלייקרס לגבור על הקינגס, 112:106, בהארכה והתקדמו לגמר ה-NBA.
בגמר ה-NBA פגשו הלייקרס את ניו ג'רזי נטס, בסדרה שהייתה לפרוטוקול בלבד כאשר הלייקרס מנצחים בסוויפ, 4:0, באחת מסדרות גמר ה-NBA החד צדדיות בהיסטוריה של ה-NBA. לאחר שזכו באליפות השלישית ברציפות שלהם, זכה שאקיל אוניל בתואר ה-MVP של סדרת הגמר בפעם השלישית ברציפות, הישג אותו הצליח להשיג רק מייקל ג'ורדן לפניו, והמאמן הראשי פיל ג'קסון זכה באליפות התשיעית בקריירה, כשהוא משתווה למאמנה האגדי של בוסטון סלטיקס, רד אאורבך, וכשהוא עובר את פט ריילי כמאמן עם מספר הניצחונות הרב ביותר בפלייאוף.
הלייקרס נראו הרסניים ובלתי ניתנים לעצירה, והקבוצה שמה לה למטרה אליפות רביעית ברציפות. אך, הלייקרס התחילו את עונת בצורה חלשה כששאקיל אוניל מחמיץ 12 משחקים לאחר שעבר ניתוח בבוהן כף רגלו, ולאחר מכן נאלץ לחזור לאיטו לכושר משחק. בחג המולד, הגיעו הלייקרס למאזן 11:19, אז החל קובי בראיינט לשאת את הקבוצה על גבו באחת מהתקופות הטובות בקריירה שלו, כשהוא קובע שיא NBA לשחקן הצעיר ביותר המגיע ל-10,000 נקודות, הוא קבע שיא NBA חדש עם 12 קליעות ל-3 נקודות במשחק בודד, שיא של 8 סלי 3 נקודות במחצית אחת, 9 סלי 3 נקודות רצופים במשחק אחד, בנוסף קבע בריאנט שיא מועדון של 42 נקודות במחצית אחת, קלע יותר מ-40 נקודות בתשעה משחקים רצופים (כשהוא מצטרף לוילט צ'מברלין ומייקל ג'ורדן), קלע יותר מ-35 נקודות ב-13 משחקים רצופים (כשרק צ'מברלין עובר אותו בהישג זה), הפך לשחקן שלישי בהיסטוריה של ה-NBA המשיג ממוצע של 40 נקודות במשך חודש שלם, והשיג טריפל דאבל פעמיים ברציפות, לראשונה מאז מג'יק ג'ונסון ב-1991.
הלייקרס סיימו את העונה הסדירה במאזן 50:32, עונת ה-50+ ניצחונות ה-27 מאז עבר המועדון ללוס אנג'לס. בפלייאוף, גברו הלייקרס על מינסוטה טימברוולבס בשישה משחקים, 4:2. בחצי גמר המערב פגשו הלייקרס את סן אנטוניו ספרס והרגע המכריע של הסדרה הגיע במשחק החמישי לאחר שהסדרה הייתה בשוויון 2:2, הלייקרס כבר סבלו מהעדרו של ריק פוקס, שסבל מפציעה זכר לסדרה מול מינסוטה. במשחק, הספרס כבר ברחו ל-25 נקודות יתרון, לפני שהלייקרס החלו להתאושש ולנגוס ביתרון, את הרבע הרביעי פתחו הלייקרס בפיגור של 18 נקודות ועתה החלו לדהור ולנגוס ביתרון הספרס במהירות, וכאשר נותרו 14.7 שניות לסיום המשחק פיגרו הלייקרס רק ב-2 נקודות, עתה נפל המשחק על כתפיו של האיש אליו נטו הלייקרס ללכת ברגעי ההכרעה, לאחר שהכריע כמה וכמה משחקים בזריקות מעבר לקשת ה-3 במהלך סדרות פלייאוף מהעונה הקודמת, וכאשר נותרו 3.6 שניות לסיום המשחק שחרר רוברט הורי זריקת 3 נקודות שהייתה יכולה לנצח במשחק בעבור הלייקרס – אך הפעם ראו הלייקרס את הכדור פוגע בטבעת הסל ונכנס ויוצא אל מחוץ לטבעת. זריקה שתמיד הייתה נכנסת לא הייתה כזו הפעם.
במקום לשמוח שוב על ניצחון שהושג בשניות האחרונות וביתרון 3:2 בסדרה שבידם ישנה האפשרות להכריע את הסדרה במשחק השישי שהתקיים בלוס אנג'לס, מצאו הלייקרס את עצמם במשבר לאחר שהיו כל כך קרובים להכריע את הסדרה, עתה כשהם בפיגור 2:3 בסדרה ועל סף הדחה מהמשך משחקי הפלייאוף. הספרס לא בזבזו את ההזדמנות שנפלה לידיהם וגברו על הלייקרס גם במשחק השישי הסדרה, וניצחו בסדרה כולה 4:2, משאירים את הלייקרס עם חלום מנופץ לאליפות רביעית ברציפות.
נחושים להשיב לעצמם את תואר האליפות בשנה ה-25 לבעלות של ג'רי באס על הלייקרס, הביאו הלייקרס את השחקנים החופשיים, קארל מלון וגארי פייטון, והחלו את עונת בסערה, כשהם מנצחים 20 מ-25 המשחקים הראשונים, כאשר באותו הזמן הפך קארל מלון לשחקן הוותיק ביותר המשיג טריפל דאבל. אך זמן קצר לאחר מכן נפצע מלון בברכו, והיעדרויות עקב פציעות ומחלות של שאקיל אוניל וקובי בראיינט הגיעו זמן קצר אחר כך, כתוצאה מכך נותר גארי פייטון לבדו כדי להוביל את התקפת הלייקרס יחד עם השחקנים הצעירים בשיטה אליה לא היה רגיל. בנוסף סבלה הקבוצה מהטרדה מתמשכת עקב פרשיית התקיפה המינית של קובי בראיינט וההצלפות ההדדיות בין אוניל לבראיינט שהחלו לאחר שהוגש כתב אישום נגד בראיינט.
למרות זאת, הצליחה הקבוצה להחזיק מעמד עד אשר כולם התאוששו, כשהם מסיימים את היישורת האחרונה של העונה בסטייל עם 14 ניצחונות ב-17 המשחקים האחרונים, בדרך למאזן 56:26 בסיומה של העונה הסדירה, ותואר אליפות הבית הפאסיפי הודות לשני סלים עם הבאזר במשחק מול פורטלנד: אחד שהשווה את תוצאת המשחק בתום הזמן החוקי, והשני שניצח במשחק לאחר הארכה כפולה. בפלייאוף, ללא רוברט הורי, גברו הלייקרס בסיבוב הראשון על יוסטון רוקטס בחמישה משחקים, 4:1. בחצי גמר המערב פגשו הלייקרס את סן אנטוניו ספרס, ושוב מצאו את עצמם בפיגור 0:2 (שהגנה על כתר האליפות שלה), והצליחו הלייקרס להשוות אתה סדרה לאחר שני משחקי בית. במשחק החמישי נקלעו הלייקרס לפיגור כאשר המשחק התקרב לסיומו, וללא הורי נזקקו הלייקרס לדרק פישר כדי שיושיע אותם לאחר שהצליח לתפוס את הכדור ממסירת החוץ ולזורקו תוך כדי סיבוב כאשר נותרו רק 0.4 שניות לסיום, ברגע שזכה להכרה כאחד הרגעים המדהימים בהיסטוריה של ה-NBA. לאחר שניצחו במשחק החמישי 74:73 בסן אנטוניו, השלימו הלייקרס את המשימה כשגברו על הספרס גם במשחק השישי בסדרה שנערך בלוס אנג'לס, 88:76, ובסדרה כולה 4:2 והתקדמו לגמר המערב. בגמר המערב פגשו הלייקרס את המדורגת ראשונה מינסוטה טימברוולבס עליהם גברו בקלות יחסית 4:2, כדי לפגוש את דטרויט פיסטונס בגמר ה-NBA. בגמר ה-NBA הופתעו הלייקרס שנחשבו לפייבוריטים מול הפיסטונס, כאשר הפיסטונס השתלטו במהרה על הסדרה במשחקם הקבוצתי ובהגנה העוקצנית שהציגו וגברו על הלייקרס בחמישה משחקים, 4:1.
2004–2007: בניה מחדש.
בקיץ שלאחר עונת 2003/2004, קרסו הלייקרס כלפי פנים. המאמן הראשי פיל ג'קסון היה מותש, והנהלת הלייקרס לא הייתה מוכנה להעלות את משכורתו מ-6 מיליון דולר ל-12 מיליון אותם דרש כדי להמשיך בתפקידו. כמו כן, עוזר המאמן טקס וינטר אמר כי ג'קסון הכריז בפגרת אולסטאר 2004 כי לא יהיה מעוניין לחזור ללוס אנג'לס לייקרס אם קובי בראיינט יישאר. המתח ההולך וגובר בין שאקיל אוניל לקובי בראיינט הגיע לבסוף לנקודת רתיחה. כאשר נודע כי ג'קסון לא יישאר בתפקידו (מהלך שרבים מאמינים כי לבראיינט הייתה יד בדבר), דרש שאקיל אוניל טרייד שניתן לו בסופו של דבר והוא הועבר למיאמי היט בתמורה ללמאר אודום, קארון באטלר, ובריאן גרנט. בראיינט בחן את שוק השחקנים החופשיים, כשלכאורה היה קרוב מאוד לחתימה ביריבה העירונית לוס אנג'לס קליפרס לפני שהחליט להישאר בלייקרס. פיל ג'קסון פרש לחוותו במונטנה ורודי טומג'נוביץ' מונה למאמן הראשי החדש של הקבוצה.