Peristiwa rusuhan kaum 13 Mei 1969 menimbulkan kesedaran tentang pelbagai pihak mengenai pentingnya menguruskan perbezaan dan kepekaan yang wujud dalam komuniti berbilang kaum seperti Malaysia. Berikutan kejadian ini, Majlis Gerakan Negara (MAGERAN) ditubuhkan. Kewujudan MAGERAN adalah untuk meningkatkan keselamatan awam, pertahanan negara dan keamanan pemeliharaan untuk orang awam, bekalan dan perkhidmatan yang kritikal kepada negara. Apabila keadaan bertambah baik, MAGERAN dibubarkan pada awal tahun 1971.[1]

Walau bagaimanapun, Kerajaan merasakan kewujudan badan/agensi yang bertanggungjawab untuk pengurusan hal-hal keselamatan di peringkat nasional, negeri dan daerah diperlukan kerana terdapat ancaman komunis dan hubungan antara kaum masih rapuh. Pada 23 Februari 1971, Kerajaan telah menubuhkan Majlis Keselamatan Negara untuk menyelaraskan dasar yang berkaitan dengan keselamatan negara dan memberi arahan mengenai keselamatan termasuk pergerakan keselamatan, keamanan awam dan semua perkara yang berkaitan dengan keselamatan.[2]

Pejabat Sekretariat Majlis Keselamatan Negara ditubuhkan untuk menjalankan tugas administrasi dan kesetiaan untuk Majlis Keselamatan Negara. Pada tahun 1995, Pejabat Majlis Keselamatan Negara telah disusun semula sebagai Bahagian Keselamatan Kebangsaan (BKN) di mana Pejabat Sekretariat Keselamatan Negeri dan Pejabat Sekretariat Keselamatan Daerah berada di bawah bidang kuasa Jabatan Perdana Menteri dan selepas itu mengalami perubahan nama kepada Negara Negeri dan Daerah Bahagian Keselamatan. Bahagian Keselamatan Negara bertanggungjawab untuk menyelaraskan dasar yang berkaitan dengan keselamatan serta mengarahkan tindakan yang diperlukan oleh agensi yang berkaitan.

Pada 24 Julai 2007, Bahagian Keselamatan Negara sekali lagi disusun semula dan menjadi Majlis Keselamatan Negara, di mana Bahagian Keselamatan Negeri menjadi Majlis Keselamatan Negeri dan Bahagian Keselamatan Daerah menjadi Majlis Keselamatan Daerah. Penyusunan semula adalah untuk memastikan bahawa Majlis Keselamatan Negara melaksanakan fungsinya sebagai pembuat polisi yang berkaitan dengan keselamatan negara dan untuk memberi arahan mengenai keselamatan secara keseluruhannya.

Pada 26 Oktober 2016, satu Pasukan Petugas Keganasan Operasi Khas telah ditambah di bawah MKN sebagai tindak balas terhadap aktiviti keganasan global. Unit pertama di dunia adalah gabungan Pasukan Operasi Khas antara Angkatan Bersenjata Malaysia, Polis Diraja Malaysia dan Agensi Penguatkuasaan Maritim Malaysia.[3]