Wali dibentuk pada tanggal [[31 Oktober]] [[1999]] dengan nama '''Fiera'''. Nama band awalnya di ambil dari inisial huruf personelnya yang terdiri dari Faank (vokal), Tomi (drum), Endang (bass), Ridho (gitar rhythm gitar), dan Apoy (lead gitar).
Pada tahun 20062005 mereka sempat memiliki single yang bertajuk Maafkan Aku Tak Setia, namun di awalpertengahan tahun 20072006 Endang dan Raden tidak dapat lagi bergabung dengan mereka, karena ada kesibukan masing masing. Hengkangnya Endang dan Ridho meninggalkan masalah bagi Fiera band, pasalnya mereka kehilangan personel yang mengisi gitar 2. Namun permasalahan itu dapat terselesaikan dengan langkah efisiensi yakni menggantikan gitar 2 dengan keyboard synthesizer untuk mempertebal harmonisasi lagu, dengan bergabungnya Ovie pemain keyboard dan Nunu sebagai pembetot bass, nama Fiera berganti menjadi Wali. Dengan formasi itu Wali berhasil menembus dunia rekaman dengan album perdana yang dirilis pada tahun 2008.
