Majlis Raja-raja ditubuhkan secara formalnya dalam tahun 1948 apabila Persekutuan Tanah Melayu diwujudkan. Sebelum Persekutuan wujud, sembilan Negeri-negeri Melayu dan dua Negeri-negeri Selat (British Straits Settlements) telah ditadbir sebagai Malayan Union di bawah pemerintah tertinggi seorang Gabenor British, iaitu antara 01.04.1946 dan 31.01.1948. Singapura yang juga adalah sebuah Negeri Selat telah dipisahkan sebagai Tanah Jajahan British (British Crown Colony). Malayan Union menggantikan Pentadbiran Tentera British (British Military). Administration (September 1945-April 1946) yang memerintah sementara selepas kekalahan Jepun yang menakluki Negara ini dari akhir 1941 hingga September 1945.
Sebelum itu Negeri-negeri di Semenanjung di perintah secara berlainan iaitu terdapat lima Negeri Melayu yang tidak bergabung (Kedah, Perlis, Kelantan, Terengganu dan Johor manakala empat pula bergabung sebagai Negeri-negeri Melayu Bersekutu (Federated Malay States) terdiri daripada Pahang, Perak, Selangor dan Negeri Sembilan antara 1896 dan 1941 dan juga tiga Negeri-negeri Selat iaitu Pulau Pinang, Melaka dan Singapura.
Negeri-negeri Melayu Bersekutu menganjurkan Durbar iaitu forum bersama antara Raja-raja dan pihak pentadbir British yang bermesyuarat dari masa ke masa. Durbar itulah precursor iaitu pelopor kepada Majlis Raja-raja sekarang.
Gelaran “Penyimpan Mohor Besar Raja-raja” (“The Keeper of the Rulers’ Seal”), dibawa jauh dari England ke Malaysia melalui India. Ia berasal dari Britain dan berakar umbi lebih 600 tahun dahulu. Beliau dikenali dengan nama ini memandangkan beliaulah yang menjaga Mohor Besar Raja-raja. Tidak banyak orang yang mengetahui tugas yang dijalankan oleh Penyimpan Mohor Besar Raja-raja ini. Sebenarnya beliau merupakan Setiausaha Majlis Raja-raja (Seksyen 4 Jadual Kelima dalam Perlembagaan Persekutuan).
