Keretakan hubungan Shaquille O'Neal dan Kobe Bryant sempat membuat Lakers putus prestasi. O'Neal sendiri memilih hengkang ke Miami Heat pada 2004. Kepindahan itu sekaligus mengakhiri Shaq/Kobe Era.
Sementara itu, Bryant bertahan di Staples Center. Dia bahkan bertahan selama 20 tahun bersama Lakers. Klub Los Angeles itu merupakan satu-satunya klub yang pernah ia bela selama kariernya.
Hanya saja, sepeninggalan O'Neal, Bryant tidak lagi merasakan gelar juara NBA sampai 2009. Apalagi dia juga sempat bermasalah dengan urusan di luar lapangan. Bryant tersandung kasus kekerasan seksual yang menyeretnya ke pengadilan.
Masalah itu belum ditambah kepergian Phil Jackson. Pada 2004, dia meninggalkan klub Los Angeles. Jackson sempat bingung dengan masalah yang ada di klubnya, terutama masalah Kobe Bryant.
Meski begitu, Master Zen kembali pada 2005 setelah Rudy Tomjanovich, pelatih yang sempat menggantikannya, mengalami masalah kesehatan. Jackson bahkan memperpanjang kontraknya hingga dua tahun pada 2007.
"Menurut pendapat kebanyakan orang di bola basket, dan tentu saja menurut kami, Phil adalah pelatih terhebat dalam sejarah NBA, dan kami senang dia memutuskan untuk tinggal bersama Lakers untuk waktu yang lama," kata pemilik Lakers, Dr. Jerry Buss, seperti dikutip situs resmi NBA.
"Sederhananya, dia adalah pelatih terbaik dalam bisnis ini dan dia akan menjadi bagian berharga dari pengembangan tim kami saat kami terus berkembang."
Bryant, yang sempat tersandung masalah, pun berhasil memulihkan kariernya. Dia mengintrospeksi diri sehingga tidak terjerumus lebih dalam lagi. Bryant mengganti nomor punggungnya dari 8 ke 24 pada 2006/2007. Perlahan-lahan Lakers kembali ke bentuk semula bersama jati diri Kobe Bryant yang baru.
Pada 2008, Lakers sebenarnya punya kans untuk menjadi juara lagi. Mereka kedatangan Pau Gasol dari Memphis Grizzlies yang menjadi tambahan amunisi penting di Los Angeles. Bryant dan Gasol bahu-membahu mengantarkan Lakers ke Final Wilayah Barat untuk menekuk San Antonio Spurs, juara NBA 2007.
Sayangnya, perjalanan mereka harus terhenti setelah Boston Celtics mengubur asa Lakers di Final NBA. Celtics mengalahkan Lakers dengan kedudukan 4-2. Publik Los Angeles ditampar keras-keras.
Kekalahan atas seteru abadi itu kemudian membakar semangat Kobe Bryant. Dia segera bangkit dan mendorong rekan-rekan setimnya untuk melakukan hal yang sama. Semusim setelah kegagalan mereka di Final NBA 2008, Bryant dkk. keluar sebagai juara. Mereka mengalahkan Orlando Magic dengan kedudukan 4-1 pada 2009.