Lagu ini diadopsi dari melodi lagu resmiKesultanan Perak bernama "Allah Lanjutkan Usia Sultan", yang sebenarnya juga merupakan adaptasi dari melodiLagu Terang Bulan dan terutama lagu berjudul "La Rosalie", gubahan komposer berkebangsaanPrancis,Pierre Jean de Beranger. MulanyaTunku Abdul Rahman,PM Malaya saat itu, sudah mengadakan sayembara khusus demi menemukan lagu kebangsaan negara baru ini, namun dari 514 proposal yang dikirim, tidak ada yang dirasa pas. Tunku lalu melihat bahwa lagu Allah Lanjutkan Usia Sultan dirasa lebih "tradisional", dan berhasil membujuk panitia sayembara untuk menetapkan lagu tersebut sebagai lagu kebangsaan Malaysia di tanggal 5 Agustus 1957 dalam sebuah rapat di Kantor Polisi Depoh,Kuala Lumpur.[2][3]
Setelah melodi didapatkan, sayembara lainnya dibuka untuk menciptakan liriknya yang berhadiah 1.000ringgit. Versi yang terpilih adalah karanganSaiful Bahri, yang kemudian diperdengarkan secara resmi ketika deklarasi kemerdekaan Malaya di tanggal 31 Agustus 1957. Setelah Malaysia berdiri, Negaraku tercatat dua kali diaransemen kembali, di tahun 1992[4] dan 2003.[5][6]