Meskipun saat itu musik KLa Project lebih maju dari zamannya, karena musik dengan irama melayu masih populer, mereka berhasil mencuri hati banyak pendengar musik. Mereka pun memiliki basis penggemar yang menamakan diri ''KLanis'' (KLanese).
Setelah peluncuran album ketiga, Ari Burhani keluar dan beralih peran sebagai manajer band. KLa kemudian berjalan dengan formasi 3 orang dan merilis 2 album keempat dengan bantuan '''additional drummer''' yaitu [[Ungu (album)|Ungu]] (1994) dengan bantuan [[Ronald Fristianto]] dan(drummer [[Dr.PM]], eks drummer [[Gigi (grup musik)|GIGI]]). Setahun kemudian, KLa merilis album kelima [[Kelima (album)|V]] (1995) dengan bantuan [[Aksan Sjuman|Wong Aksan]] (drummer [[Potret (grup musik)|Potret]], eks drummer [[Dewa 19]]) dan [[Rere Reza|Rere]] (drummer [[Grass Rock]]). Pada akhir tahun 1996, KLa Project menggelar konser akustik akbar bertajuk [[KLakustik]] yang melibatkan musisi pendukung seperti Edi Kemput (gitar), Danny Supit (bass), [[Hendri Lamiri]] (biola), [[Budhy Haryono]] (drum), Adjierao (perkusi) dan lain-lain. Konser ini digelar di Gedung Kesenian Jakarta yang disiarkan oleh [[Antv|ANTV]], yang kemudian mereka rekam secara live dan dirilis dalam bentuk album rekaman 2 jilid.<ref>[http://indolawas.blogspot.com/2009/01/kla-project-klakustik-2.html Tentang konser KLakustik]</ref>
Pada bulan Maret 2001, giliran [[Lilo]] yang memutuskan untuk keluar dari band ini. Namun, KLa tetap berjalan terus walau hanya menyisakan [[Katon Bagaskara]] dan [[Adi Adrian]]. Kemudian tahun 2003, KLa memutuskan untuk menambah 3 personel baru, yaitu [[Erwin Prasetya]] (bass, eks bassist [[Dewa 19]]), [[Yoel Vai]] (gitar) dan Harry Goro (drum, additional drummer KLa Project). Dengan formasi terbaru , nama KLa pun berubah menjadi '''NuKLa'''. NuKLa sempat mengeluarkan 1 album yang berjudul "[[New Chapter]]" (2004) dengan single ''Izinkan Ku Memuja''. Pada tahun 2005, NuKLa merilis album "[[New Chapter|New Chapter For Aceh]]" dengan tambahan 2 lagu baru yaitu ''Dukamu Dukaku'' dan ''Kau Tak Pernah Sendiri''.
Pada tahun 2006, [[Erwin Prasetya]] memutuskan untuk keluar dari NuKLa karena perbedaan visi misi. Kemudian, disusul hengkangnya Harry Goro dan [[Yoel Vai]]. Tak lama setelah itu, [[Katon Bagaskara]] menyatakan bahwa NuKLa berganti nama kembali menjadi '''KLa Project'''. Salah satu alasannya adalah sulitnya mengubah citra KLa yang lama menjadi baru.
