Perdana Menteri Persekutuan Tanah Melayu, Tunku Abdul Rahman Putra dalam satu ucapan beliau di Persidangan Persatuan Wartawan Luar Negeri Asia Tenggara yang diadakan di Hotel Adelphi, Singapura pada 27 Mei 1961, telah menggagaskan tentang perlunya diwujudkan satu rancangan untuk membawa Persekutuan Tanah Melayu, Singapura, Borneo Utara, Brunei dan Sarawak ke dalam satu bentuk kerjasama politik dan ekonomi. Antara lain, kerjasama ini perlu diadakan adalah bertujuan untuk menyekat pengaruh komunis yang semakin ketara yang boleh menggugat kestabilan politik serantau. Pendirian kerajaan ini adalah berdasarkan kepada perkembangan politik di Singapura yang memperlihatkan peningkatan pengaruh golongan kiri. Di samping itu juga gagasan ini bertujuan untuk mengimbangi jumlah penduduk, meningkatkan kemajuan ekonomi dan mempercepatkan proses kemerdekaan bagi Singapura, Brunei, Borneo Utara dan Sarawak.
Mesyuarat Persatuan Parlimen Komanwel Cawangan Tanah Melayu dan Borneo di Singapura pada 23 Julai 1961 telah bersetuju menubuhkan Jawatankuasa Perundingan Perpaduan Malaysia dengan dipengerusikan oleh Donald Stephen. Tujuan penubuhan Jawatankuasa ini adalah untuk menerangkan dengan lebih jelas tentang konsep Malaysia kepada orang ramai khususnya penduduk Sabah, Sarawak dan Brunei. Dalam Jawatankuasa ini, perwakilan dari Tanah Melayu terdiri daripada ahli-ahli Parlimen. Perwakilan Singapura terdiri daripada ahli-ahli Majlis Mesyuarat Undangan termasuk seorang ahli parti pembangkang. Anggota perwakilan dari Sarawak adalah ahli-ahli Majlis Negeri Sarawak, begitu juga dengan Sabah. Jawatankuasa ini telah bermesyuarat sebanyak empat kali untuk membincangkan perkara-perkara berkaitan penubuhan Malaysia. Mesyuarat pertama diadakan di Sabah pada Ogos 1961, seterusnya di Kuching, Sarawak pada Disember 1961 dan di Kuala Lumpur pada Januari 1962. Mesyuarat terakhir telah diadakan di Singapura pada Februari 1962. Dalam mesyuarat terakhir itu Jawatankuasa bersetuju untuk mengemukakan memorandum kepada Suruhanjaya Cobbold supaya dibuat tinjauan mengenai pandangan penduduk di Sarawak dan Sabah terhadap gagasan Malaysia
Memorandum yang dipersetujui Jawatankuasa tersebut mengandungi beberapa perkara penting untuk dijadikan asas kepada perlembagaan yang akan dirancang. Jawatankuasa ini bersetuju supaya perlembagaan Tanah Melayu dijadikan asas kepada perlembagaan Malaysia. Antara perkara lain yang dipersetujui ialah tentang perlunya ada sebuah kerajaan Persekutuan yang kuat dan berkuasa dalam hubungan luar, pertahanan dan keselamatan juga mengenai agama Islam diterima sebagai agama rasmi.
Pembentukan Suruhanjaya Cobbold pada 17 Januari 1962 adalah bagi memberi kebebasan dan keadilan kepada semua pihak. Suruhanjaya ini dibentuk hasil perundingan diantara kerajaan Persekutuan Tanah Melayu dan Kerajaan British pada November 1961. Tujuan penubuhan Suruhanjaya ini adalah untuk meninjau pandangan penduduk negeri-negeri di Borneo Utara (Sabah) dan Sarawak tentang gagasan Malaysia. Suruhanjaya ini dianggotai oleh lima orang ahli dengan dipengerusikan oleh Lord Cobbold, bekas gabenor Bank England, ahli-ahlinya terdiri daripada Dato’ Wong Pow Nee dan Encik Mohd Ghazali bin Shafie, sebagai wakil kerajaan Persekutuan Tanah Melayu, manakala Sir Anthony Abell dan Sir David Watherston, wakil kepada kerajaan British. Mr. H. Harris bertindak selaku Setiausaha.
Sepanjang Februari-hingga April 1962, Suruhanjaya ini telah menemui lebih 4000 orang dan menerima 2200 memorandum daripada pelbagai pihak yang terdiri dari parti-parti politik, ahli-ahli Mesyuarat Kerajaan dan Undangan, pembesar-pembesar, anak-anak negeri dan pemimpin kaum, majlis bandaran, pemimpin-pemimpin agama, kesatuan sekerja dan orang ramai yang memberikan pandangan. Hasil dari laporan ini menunjukkan sejumlah 80 peratus penduduk Sarawak dan Borneo Utara menyokong kepada penubuhan Malaysia. Sokongan rakyat ini jelas dibuktikan melalui laporan Suruhanjaya Cobbold yang telah disahkan oleh perwakilan Setiausaha Bangsa-Bangas Bersatu. Selain itu, laporan itu juga memuatkan cadangan-cadangan daripada ahli-ahli Suruhanjaya berhubung beberapa perkara yang dinyatakan melalui memorandum-memorandum yang diterimanya.
Pada 21 Jun 1962 laporan ini telah dikemukakan kepada Kerajaan British dan Kerajaan Persekutuan Tanah Melayu. Setelah dikaji, kedua-dua kerajaan bersetuju menerima hampir semua cadangan yang telah dibuat oleh Suruhanjaya tersebut. Tunku Abdul Rahman Putra, Perdana Menteri Tanah Melayu juga menerima laporan Suruhanjaya Cobbold. Beliau telah membentuk sebuah Jawatankuasa untuk mengkaji laporan itu yang telah dipengerusikan oleh beliau sendiri dan anggota-anggota yang lain terdiri dari Tun Abdul Razak (Timbalan Perdana Menteri), Tan Siew Sin (Menteri Kewangan), Datuk (Dr) Ismail Dato’ Abdul Rahman (Menteri Keselamatan Dalam Negeri) dan Datuk V.T. Sambanthan (Menteri Kerja Raya dan Telekom). Kata sepakat telah dicapai oleh Perdana Menteri Persekutuan Tanah Melayu, Tunku Abdul Rahman dan Harold Macmillan, Perdana Menteri British untuk mengadakan rundingan di London. Rundingan tersebut telah berlangsung selama 2 minggu. Pada Julai 1963 satu perjanjian penting telah ditandatangani di Pejabat Perhubungan Komanwel di Malborough House, London. Perjanjian Penubuhan Persekutuan Malaysia ini telah ditandatangani oleh wakil-wakil kerajaan British, Persekutuan Tanah Melayu, Sabah, Sarawak dan Singapura. Persetujuan telah diperolehi untuk menubuhkan Malaysia pada 31 Ogos 1963. Walau bagaimanapun, penubuhan Malaysia yang dirancang pada tarikh tersebut terpaksa ditangguhkan kerana laporan Setiausaha Bangsa-Bangsa Bersatu hanya dapat disiapkan pada 14 September 1963. Malaysia akhirnya diisytiharkan pada 16 September 1963.
Upacara pengisytiharan Malaysia telah diadakan di Stadium Merdeka Kuala Lumpur pada 16 September 1963. Upacara gilang gemilang ini telah dihadiri oleh SPB Yang di-Pertuan Agong, Raja-raja Melayu, Gabenor Pulau Pinang, Melaka, Singapura, Sarawak dan Sabah. Upacara ini juga dihadiri oleh anggota kabinet, diplomat asing di Kuala Lumpur serta jemputan khas.
Pengisytiharan penubuhan Malaysia telah dibacakan oleh Perdana Menteri, Tunku Abdul Rahman Putra di hadapan lebih kurang 30,000 rakyat Malaysia yang turut meraikan hari bersejarah tersebut. Tunku kemudiannya melaungkan “Merdeka” sebanyak tujuh kali diselang seli dengan laungan oleh rakyat yang hadir. Upacara diakhiri dengan bacaan doa selamat oleh Mufti Negeri Sembilan, Tuan Haji Ahmad bin Mohammad Said.