Therefore, on 30 July 1957, in a meeting of the Federal Executive Council, an idea to build a national mosque as a symbol of the country's independence was mooted.

In another meeting on 5 March 1958 of Chief Ministers of the eleven states in the Federation of Malaya, a proposal was made to name the mosque Masjid Tunku Abdul Rahman Putra Al-Haj, in recognition of Prime Minister Tunku Abdul Rahman's efforts in guiding the country to gaining independence.

However, Tunku refused this honour; on the contrary, he named it Masjid Negara in thanksgiving for the country's peaceful independence without bloodshed.

[1] The original structure of the mosque was designed by a three-person team from the Public Works Department: UK architect Howard Ashley, and Malaysians Ikmal Hisham Albakri [ms] and Baharuddin Kassim.

On Friday, 27 August 1965, the mosque was declared open by the third Yang di-Pertuan Agong, the late Tuanku Syed Putra of Perlis.