Gw mau tau Langkah Baru (2004–2006) dari Radja (grup musik)

Lepas dari Malta Music Indonesia, radja lalu mencari mayor label yang mau menaungi mereka. Ternyata keberuntungan mulai berpihak kepada mereka berempat, pada akhir tahun 2004, mereka dipercayakan untuk menjadi grup band yang dinaungi oleh EMI Music Indonesia. Setelah bergabung dengan EMI Music Indonesia, radja langsung mengeluarkan album repackage dari album mereka sebelumnya, karena album kedua radja dinilai memiliki nilai jual yang bagus namun tidak terpromosikan saat itu. Tanpa membuang waktu lama, mereka pun meluncurkan album repackage yang diberi judul "Langkah Baru" yang berisikan lagu-lagu mereka di album sebelumnya ditambah dengan 3 buah lagu baru, pada awal tahun 2005. Album ketiga radja ini sungguh di luar dugaan, perjualannya tidak hanya bagus, malah mampu melewati target penjualan saat itu. Lagu hits mereka "Jujur" hampir setiap hari terdengar di mana-mana, nama para personel radja pun mulai dikenal oleh masyarakat. Album ketiga ini memang di luar prediksi mereka. Album "Langkah Baru" membawa radja meraih Golden Award untuk penjualan kaset di atas 75.000 copy, Platinum Award untuk penjualan di atas 150.000 copy, Double Platinum Award untuk penjualan di atas 300.000 copy, Multi Platinum untuk penjualan kaset di atas 500.000 copy yaitu sebanyak 1,2 juta copy. Prestasi yang tidak pernah mereka raih sebelumnya ketika mereka mampu meraih semua penghargaan itu.

Aku Ada Karena Kau Ada dan 1000 Bulan (2006–2007)

Pada tahun 2006 mereka pun meluncurkan album keempat mereka yang bertajuk "Aku Ada Karena Kau Ada". Sekali lagi album inipun mendapat respon yang cukup baik dalam masyarakat Indonesia. Lagu-lagu radja semakin merakyat dalam masyarakat Indonesia baik di kota-kota besar maupun di pelosok daerah. Bahkan mereka pernah tampil menghibur masyarat Indonesia bagian timur seperti masyarakat di daerah Luwuk dan Papua. Tidak hanya di dalam negeri, mereka pun mampu memukau masyarakat negara tetangga, seperti Malaysia dan Brunei.

Beberapa penghargaan pun kembali mereka peroleh, salah satunya mereka peroleh dari ajang SCTV Music Awards yang menobatkan mereka sebagai "Band Paling Ngetop 2006". Di akhir tahun 2006, kembali mereka berkarya dengan turut berpartisipasi menciptakan album religi yang diluncurkan pada saat bulan ramadhan. Album Religi ini merupakan album kelima radja dan diberi judul "1000 Bulan".