Pada 2 Januari 1956, 'Rombongan Kemerdekaan' pimpinan Tunku yang mewakili Perikatan yang terdiri daripada Tunku sendiri, S.H. Lee dan T.H. Tan di satu pihak dan satu pihak lagi mewakili Raja-raja Melayu iaitu Dato Panglima Bukit Gantang (Menteri Besar Perak), Abdul Aziz Abdul Majid (Menteri Besar Selangor), Dato' Wan Idris Wan Ibrahim (Timbalan Menteri Besar Johor) dan Dato' Nik Ahmad Kamil (bekas Menteri Besar Kelantan) telah berlepas ke Karachi dengan kapal Ital 'Asia' dan kemudiannya dengan kapal terbang ke London.

Pada 18 Januari 1956 rundingan kemerdekaan pun bermula. Pihak kerajaan British diwakili oleh Allen Lennox Boyd. Rundingan tersebut mencakupi pelbagai masalah termasuklah masalah Raja-raja Melayu, kedudukan pegawai-pegawai awam British yang sedang berkhidmat di Tanah Melayu dan lain-lain langkah peralihan yang perlu diputuskan sebelum kemerdekaan serta tarikh kemerdekaan yang menurut Tunku perlu disegerakan. Perundingan itu tamat setelah diadakan selama tiga minggu dengan kejayaan cemerlang di pihak Tunku Abdul Rahman. Pada 6 Februari 1956, beliau telah menurunkan tandatangan atas perjanjian 'Merdeka' bersama Lennox Boyd dalam satu istiadat sederhana di Lancester House.

Dua minggu setelah kembali ke Kuala Lumpur, tunku telah mula memegang Kementerian Pertahanan dan Keselamatan Dalam Negeri. Beliau menjadi Pengerusi Majlis Gerakan Menghapuskan Darurat. Dalam pada itu berbagai-bagai masalah timbul mengenai soal hak kerakyatan dan satu undang-undang kerakyatan umum. Islam diterima sebagai agama rasmi dan rakyat bukan Melayu bebas mengamalkan agama mereka.

Pada malam 30 Ogos 1957, negara Malaysia penuh dengan keriangan. Beberapa minit sebelum tengah malam, Tunku Abdul Rahman tiba. Bendera Malayan Union Jack diturunkan tepat jam 12 tengah malam dan di tempatnya digantikan dengan bendera Persekutuan.