במהלך הפגרה החליט המאמן הראשי מייק דאנליבי לעזוב את המועדון לתפקיד במילווקי באקס. רנדי פונד שהיה עוזר המאמן תחת פט ריילי ומייק דאנליבי מונה למאמן הראשי. בתחילת עונת נפצע ביירון סקוט והלייקרס הגיעו למאזן מכובד של 33:29 לאחר 61 משחקים. לאחר מכן הועבר סם פרקינס בטרייד לסיאטל סופרוניקס תמורת בנויט בנג'מין והזכויות על הרוקי דאג כריסטי. הטרייד יצר מורת רוח בקרב סגל השחקנים שהיה גם כך שביר והלייקרס לא הצליחו להתעלות השיגו מאזן 6:14 ב-20 המשחקים האחרונים לעונה. את העונה הסדירה סיימו הלייקרס במאזן 39:43, אך עדיין הצליחו להשתחל את הפלייאוף. הלייקרס הפתיעו כשהצליחו לנצח בשני המשחקים הראשונים בסדרה מול פיניקס סאנס החזקה בחוץ, אך, הפסידו בשלושת המשחקים הבאים בסדרה, כאשר במשחק החמישי והמכריע בפיניקס נכנעו הלייקרס לאחר הארכה, ובסדרה כולה, 2:3.
ולאדה דיבאץ ובחירת הדראפט ניק ואן אקסל הובילו את הלייקרס בנקודות בעונת , אך הדרך הייתה מלאת מהמורות. לאחר שאיבדו את ביירון סקוט ואיי. סי. גרין הוותיקים שהפכו לשחקנים חופשיים ובעונתו האחרונה של ג'יימס וורת'י, סיימו הלייקרס את העונה הסדירה במאזן 33:49 ונכשלו בניסיון להעפיל אל הפלייאוף, לראשונה מזה 17 שנים. הלייקרס עשו ניסיון אחרון להעפיל אל הפלייאוף כאשר פיטרו את המאמן רנדי פונד ומינו מקומו את כוכבם לשעבר, מג'יק ג'ונסון כמאמן הראשי. אך לרוע מזלם של אוהדי הלייקרס, הפסיד ג'ונסון בעשרת המשחקים האחרונים של העונה, שנכון להיום מהווה את רצף ההפסדים הארוך ביותר בתולדות המועדון. כשהוא מבין כי אינו בנוי להיות מאמן, פינה מג'יק ג'ונסון את מקומו והלייקרס מינו במקומו את דל האריס כמאמן הראשי לעונת 1994/1995.
הלייקרס היו לאחת הקבוצות המשתפרות ביותר בעונת , כשהם מסיימים את העונה הסדירה במאזן 48:34 וחזרו לפלייאוף לאחר שנעדרו ממנו בעונה הקודמת. השיפור הניכר נבע מכמה סיבות, כולל הגעתו של האריס, שיפור משחקו של שחקן העונה השנייה ניק ואן אקסל, התבגרות משחקם של השחקנים המנוסים יותר, ולאדה דיבאץ ואלדן קמפבל, החתמתו של סדריק סבאלוס במהלך הפגרה, והגעתו של הרוקי אדי ג'ונס שנבחר בדראפט 1994 כבחירה העשירית, סבאלוס היה לשחקן הראשון שקולע 50 נקודות במשחק אחד במדי הלייקרס מזה 20 שנה. בפלייאוף, גברו הלייקרס בסיבוב הראשון על סיאטל סופרסוניקס, 3:1 וניצחו סדרת פלייאוף לראשונה מאז ימיו של מג'יק ג'ונסון. בחצי גמר המערב נוצחו הלייקרס בידי המדורגת ראשונה סן אנטוניו ספרס בשישה משחקים, 2:4. דל האריס נבחר למאמן השנה וג'רי וסט זכה בפרס מנהל השנה.
לעונת חזרו הלייקרס עם כמעט אותו סגל שחקנים, ובמחצית העונה עמד מאזנם על 24:18. ב-30 בינואר 1996, חזר מג'יק ג'ונסון מהפרישה כשחקן מחליף ורשם 19 נקודות, 10 אסיסטים, ו-8 כדורים חוזרים במשחק הבכורה המחודשת שלו מול גולדן סטייט ווריורס. בשבועות הראשונים לחזרתו שיחק ג'ונסון היטב והצעיד את הלייקרס למאזן 29:11 כשלבש את מדי המועדון. אך, ככל שהעונה התקדמה החלו הלייקרס להתפרק כשהגיל והשהות הארוכה מחוץ למגרש החלו לתת את אותותיהם במג'יק. קפטן הלייקרס סדריק סבאלוס הושעה על ידי המועדון, ניק ואן אקסל הושעה לשבעה משחקים לאחר שדחף שופט, ואפילו ג'ונסון איבד את קור הרוח של, כשנזרק ממשחק לקראת סופה של העונה לאחר שנתקל בשופט המשחק. הלייקרס הקורסים סיימו את העונה הסדירה במאזן, 53:29, והודחו בסיבוב הראשון בידי יוסטון רוקטס לאחר ארבעה משחקים, 1:3. בתום העונה פרש ג'ונסון שוב.
1996–2004: חזרה לתהילה: תקופת שאק וקובי.
במהלך הפגרה של 1996, רכשו הלייקרס את קובי בראיינט בן ה-17 משארלוט הורנטס תמורת ולאדה דיבאץ; בראיינט נבחר כבחירה ה-13 בדראפט 1996 היישר מהתיכון לוואר מאריון היי סקול, שבארדמור, פנסילבניה, בידי ההורנטס. הלייקרס החתימו גם סנטר אורלנדו מג'יק לשעבר שהפך לשחקן חופשי, שאקיל אוניל. הטרייד בעבור בראיינט היה רעיון של ג'רי וסט, הוא גם היה גורם רב השפעה במהלך להחתמתו של אוניל, "ג'רי וסט היה הסיבה העיקרית שהגעתי ללוס אנג'לס", אמר שאקיל אוניל מאוחר יותר. הלייקרס ניצלו את הבחירה ה-24 שעמדה לרשותם בדראפט 1996, כדי לבחור את דרק פישר. במהלך עונת , ביצעו הלייקרס טרייד על סידריק סבאלוס והעבירו אותו לפיניקס סאנס תמורת רוברט הורי. אוניל הוביל את הלייקרס למאזן 56:26, בסיומה של העונה הסדירה וזאת על אף שהחמיץ 31 משחקים בעקבות פציעה בברך. אוניל השיג 26.2 נקודות ו-12.5 כדורים חוזרים בממוצע למשחק כשהוא מסיים במקום השלישי בליגה עם 2.88 חסימות למשחק ב-51 משחקים. בפלייאוף, הדיחו הלייקרס בסיבוב הראשון את פורטלנד טרייל בלייזרס, כשאוניל קולע 46 נקודות במשחק הראשון בסדרה, מספר הנקודות הגבוה ביותר לשחקן במשחק פלייאוף מאז שג'רי וסט קלע 53 נקודות נגד בוסטון סלטיקס ב-1969, הלייקרס ניצחו בסדרה 3:1. אף על פי שיא NBA של 7 סלי 3 נקודות מ-7 ניסיונות אותו קבע רוברט הורי במשחק השני בסדרת חצי גמר המערב נגד יוטה ג'אז. הפסידו הלייקרס את הסדרה 1:4, לג'אז בה כיכבו קארל מלון וג'ון סטוקטון.
בעונה שלאחריה, , היו הלייקרס הקבוצה היחידה שאף שחקן בסגל לא היה מעבר לגיל 30 ואליהם הצטרף, ריק פוקס מבוסטון סלטיקס. הלייקרס החלו את העונה עם הפתיחה הטובה ביותר בהיסטוריה של המועדון 11:0. הלייקרס סיימו את העונה הסדירה במאזן 61:21, בפלייאוף, גברו הלייקרס בסיבוב הראשון על פורטלנד טרייל בלייזרס 3:1, ובחצי הגמר על סיאטל סופרסוניקס 4:1, בגמר המערב פגשו הלייקרס את יוטה ג'אז שהייתה בעלת המאזן הטוב ביותר במערב לאחר שסיימה את העונה הסדירה במאזן 62:20, עם ניצחון אחד יותר מאשר הלייקרס וזהה לזה של האלופה שיקגו בולס שהובילה את אזור המזרח, הסדרה הייתה חד צדדית כאשר הג'אז גברו עלה לייקרס בארבעה משחקים, 4:0 ועלו לגמר ה-NBA. הלייקרס נאבקו עם סיאטל סופרסוניקס על ראשות הבית הפאסיפי במהלך רוב העונה, ובשני החודשים האחרונים לעונה הצליחו הלייקרס לנצח 22 מ-25 המשחקים האחרונים, ולסיים במאזן 61:21 לעבור את סוניקס וזכות באליפות הביתה פאסיפי. שאקיל אוניל – על אף שהחמיץ 20 משחקים עקב פציעה בשריר הבטן – היה דומיננטי, כשהוא מסיים במקום השני בטבלת מלך הסלם של הליגה, אחרי מייקל ג'ורדן, וכמוביל הליגה באחוז הקליעה מהשדה (58.4%).
במהלך עונת , שהייתה מקוצרת עקב שביתת השחקנים, הועברו אדי ג'ונס ואלדן קמפבל בטרייד לשארלוט הורנטס תמורת גלן רייס. ניק ואן אקסל הועבר לדנוור נאגטס, דניס רודמן הראוותני הצטרף ללייקרס, על אף שהוא נחתך מהקבוצה כבר לאחר 23 משחקים. הלייקרס רכשו גם את ג'יי אר ריד, ובי. ג'יי. ארמסטרונג. המאמן האריס פוטר במהלך חודש בפברואר לאחר רצף של שלושה הפסדים והוחלף על ידי מאמן פנימי, שחק העבר של המועדון קורט רמביס. הלייקרס סיימו את העונה הסדירה במאזן 31:19, וסיימו במקום הרביעי באזור המערב. בפלייאוף, ניצחו הלייקרס את יוסטון רוקטס 3:1, אך הובסו בסוויפ בחצי גמר המערב בידי סן אנטוניו ספרס, 4:0, כהשמשחק הרביעי בסדרה היה האחרון ששוחק באולם הפורום.
תחילת תקופת פיל ג'קסון והתקפת המשולש.
עונת הביאה עימה שינויים גדולים לקבוצה: הלייקרס עברו לאולם חדש, הסטייפלס סנטר, אותו חלקו עם יריבתם העירונית לוס אנג'לס קליפרס, מדי המועדון שונו והוחלפו למדים יותר מודרניים, כשהם מחליפים את המדים הישנים של הקבוצה ששירתו אותה משנות ה-70, פיל ג'קסון מונה למאמן הראשי החדש של הקבוצה והחל להנחיל לקבוצה תפיסת התקפה חדשה: התקפת המשולש. פילוסופית המשחק החדשה התבררה כרבת עוצמה, כאשר הלייקרס פתחו את העונה בצורה חזקה, כשהם מנצחים 31 מ-36 המשחקים הראשונים של העונה, במהלך העונה הצליחו הלייקרס להשיג רצפי ניצחונות של 16, 19, ו-11 משחקים, והפכו לקבוצה השלישית בהיסטוריה של ה-NBA המצליחה להשיג שלושה רצפי ניצחונות דו סיפרתיים בעונה אחת.
על אף שהצליחו לסיים את העונה הסדירה במאזן הטוב ביותר בליגה, 67:15, ושאקיל אוניל נבחר ל-MVP של העונה הסדירה. הלייקרס מצאו את עצמם נאבקים בפלייאוף, כשהם נגררים לסדרה בת חמישה משחקים עם סקרמנטו קינגס בסיבוב הראשון, ולאחר שניצחו בחצי הגמר את פיניקס סאנס 4:1, נתקלו בקשיים רבים בסדרת גמר המערב מול פורטלנד טרייל בלייזרס, כשהם מוצאים את עצמם כבר בפיגור של 15 נקודות ברבע האחרון של המשחק השביעי והמכריע, לפני שהצליחו להתעשת ולנצח, 89:84, בסטייפלס סנטר.
בגמר ה-NBA פגשו הלייקרס את אינדיאנה פייסרס, תחת שרביט האימון של יריבה של הלייקרס משנות ה-80, לארי בירד, וגברו עליהם בשישה משחקים, 4:2 וזכו באליפות ה-12 בהיסטוריה של המועדון. שאקיל אוניל השיג 38 נקודות, 16.6 כדורים חוזרים, ו-2.3 אסיסטים בממוצע למשחק, שהוא קולע ב-61.15 מהשדה וזכה גם בפרס ה-MVP של סדרת הגמר.