Penubuhan Agensi Kawalan dan Perlindungan Sempadan Malaysia (AKPS) bermula dengan keputusan Mesyuarat Jemaah Menteri pada 16 November 2018 yang membentuk Jawatankuasa Kabinet untuk mengkaji penubuhan badan tunggal sempadan dengan Kementerian Dalam Negeri sebagai urus setia. Pada 30 Julai 2021, konsep penubuhan agensi tunggal sempadan diperkenalkan dan Pasukan Nukleus Single Border Agency (SBA) ditubuhkan berkuatkuasa pada 11 Oktober 2021. 

Seterusnya, AKPS telah ditubuhkan secara rasmi pada 1 Januari 2024 dengan 104 perjawatan asas di peringkat ibu pejabat yang diketuai oleh seorang Ketua Pengarah. Pada 3 Januari 2024, Jemaah Menteri telah meluluskan penetapan dasar AKPS, menandakan langkah penting dalam pengukuhan fungsi dan peranannya.

Rang Undang-Undang AKPS 2024 kemudiannya dibentangkan di Parlimen Malaysia dan diluluskan pada 1 Ogos 2024. Selanjutnya, ia diwartakan sebagai Akta Agensi Kawalan dan Perlindungan Sempadan Malaysia [Akta 860] pada 17 Oktober 2024, menandakan pelaksanaan undang-undang yang sah bagi mengawal selia operasi AKPS.

AKPS telah memulakan operasi rintisnya di Kompleks ICQS Rantau Panjang, Kelantan pada 1 Januari 2025 dan dijangka beroperasi di semua pintu masuk negara yang aktif menjelang tahun 2026.