SMAPL ditubuhkan pada Januari 1982 atas cadangan Pengarah Pendidikan Islam di Kementerian Pendidikan (Malaysia) pada waktu itu, Tan Sri Datuk Paduka Dr Abdul Hamid Othman. Idea ini muncul kerana kesedaran Majlis Agama Islam Wilayah Persekutuan pada ketika itu untuk membina sekolah Agama Islam di Kuala Lumpur. Selepas cadangan itu diterima oleh kerajaan, sekolah itu diberikan nama sebagai Menengah Sekolah Agama Wilayah Persekutuan (SMAWP).

SMAWP pada mulanya tidak mempunyai bangunan sendiri dan 500 orang pelajar sekolah (yang terdiri daripada pelajar tingkatan 1, 4, dan 6 rendah) menumpang di bangunan Kolej Islam Klang (KIK) di Selangor. Generasi pertama pelajar diajarkan oleh sekitar 40 guru, dipimpin oleh pengetua sekolah pertama, Tuan Hj Muhammad bin Shafie.

Selepas lebih kurang dua tahun menumpang di KIK, pada awal Januari 1984, SMAWP dipindahkan ke sebuah bangunan sementara di kampus Universiti Islam Antarabangsa Malaysia di Petaling Jaya. Pada tahun 1985, Tuan Hj Muhammad Yusof bin Abu Bakar menggantikan Tuan Hj Muhammad bin Shafie sebagai pengetua dan berkhidmat sehingga pada akhir tahun 1985. Di bawah kepimpinannya, SMAWP berjaya memenangi pertandingan Bahas Bahasa Melayu Piala Perdana Menteri pada tahun yang sama.

Pengetua seterusnya, Tuan Hj Muhd Yusof bin Hj Ahmad, meneruskan warisan SMAWP. Pada masa yang sama, Kementerian Pendidikan berjaya menyelesaikan masalah bangunan sekolah pada bulan April 1987 dengan meminjamkan sebuah bangunan di Kilometer 11, Jalan Labu yang sepatutnya digunakan sebagai bangunan Sekolah Agama Sheikh Hj Mohd Said. Selepas beberapa sesi rundingan, bangunan itu diberikan kepada sekolah secara sah, dan secara rasmi dibuka pada bulan Julai 1989 oleh Duli Yang Maha Mulia Tuanku Jaafar Ibni Almarhum Tuanku Abdul Rahman, Yang Di-Pertuan Besar Negeri Sembilan pada waktu itu. Nama SMAWP kemudian berubah menjadi Sekolah Menengah Agama Persekutuan (SMAP). Penubuhan SMAP Kajang kemudian membuat SMAP secara semulajadi dikenali sebagai SMAP Labu (SMAPL) dan kekal hingga ke hari ini. Walau bagaimanapun, tidak seperti SMAP Kajang dan SMAP Bentong, SMAP Labu tidak mempunyai perkataan Labu di dalam lencana sekolah.

Detik kegemilangan SMAP Labu semakin terserlah apabila genapnya 25 tahun penubuhannya. Sambutan Jubli Perak yang diadakan pada tahun 2007 telah menyaksikan perubahan SMAP Labu sebagai sebuah sekolah yang menjadi nadi setiap insan yang ingin membina keperibadian yang unggul serta berteraskan modal insan yang memiliki minda kelas pertama.

Kini, SMAPL telah mendapat satu lagi bangunan empat tingkat yang dikenali sebagai blok G. Beberapa kemudahan sekolah ditempatkan di sini seperti dewan terbuka, Dewan Seri Lestari, makmal Bahasa Asing yang baru, Bilik Seni Visual , beberapa buah kelas baru dan juga bilik rawatan pergigian. Di samping itu, SMAP Labu terus menjulang namanya dengan memperoleh gelaran Sekolah Kluster Kecemerlangan pada tahun 2010 dan Sekolah Berprestasi Tinggi pada tahun 2011.