Sejak tahun 2000, Pimpinan STAI Al-Qolam (belum menjadi institut) dan Ketua Yayasan Al-Qolam sudah merencanakan akan menambah program studi baru, namun hal itu belum terealisasi karena kondisi dan kemampuan belum mendukung. Impian penambahan jurusan/program studi itu baru bisa direalisasikan pada tahun 2002, yaitu dengan diterbitkannya Surat Keputusan Yayasan STAI Al-Qolam Nomor 45/SK/Y.STAI-Q/XI/2002 tentang Pembukaan Program Studi Pendidikan Agama Islam (Prodi PAI) STAI Al-Qolam. Guna memperlancar usaha tersebut, dibentuklah Panitia Pengurusan Pengajuan Penambahan Jurusan Tarbiyah (Pendidikan Agama Islam) untuk menangani proyek penambahan jurusan sebagaimana dikehendaki. Melalui perjuangan yang panjang, berliku dan melelahkan, pada akhirnya SK pendirian Program Studi Tarbiyah (Pendidikan Agama Islam) dikeluarkan oleh Departemen Agama RI pada tanggal 24 Maret tahun 2007 dengan Nomor Dj.I/179/2007. Tujuan pembukaan program studi baru ini adalah untuk menjawab kebutuhan dan perkembangan pendidikan dewasa ini.
Di usianya yang ke-11 sejak berdiri secara mandiri, STAI Al-Qolam mendapatkan momentum yang sangat bagus untuk melakukan pengembangan kelembagaan dan peningkatan kualitas pendidikan. Pada hari Jumat tanggal 15 Juni 2007, ditandatangani Nota Kesepakatan (MoU) Kerjasama Pengelolaan Pendidikan antara Universitas Islam Negeri (UIN) Malang—sebagai lembaga pembina—dan STAI Al-Qolam—sebagai lembaga binaan. Dengan adanya kerjasama pembinaan kelembagaan atas prakarsa Prof. Dr. H. Imam Suprayogo—Rektor Universitas Islam Negeri (UIN) Malang—dan K.H. Qosim Buchori—Ketua Yayasan Al-Qolam—tersebut, banyak hal yang bisa dan harus dilakukan oleh STAI Al-Qolam untuk mengembangkan diri.
Pada Tahun 2010 PS berhasil mendapatkan pengakuan penyelenggara pendidikan tinggi dari Badan Akreditasi Nasional Perguruan Tinggi (BAN-PT) melalui surat keputusan nomor 004/BAN-PT/Ak-XIII/S1/V/2010 tentang Status, Nilai, Peringkat, dan Masa Berlaku Hasil Akreditasi Program Sarjana di Perguruan Tinggi. Pada tahun 2011 PS mendapatkan Perpanjangan Izin Penyelenggaraan Program Studi Strata Satu Pada Perguruan Tinggi Agama Islam Swasta melalui Surat Keputusan Direktur Jenderal Pendidikan Islam. Dengan terbitnya surat keputusan tersebut PS semakin percaya diri untuk selalu mengembangkan tri dharma perguruan tinggi secara terus-menerus. Akhirnya, di tahun 2015 PS kembali mendapatkan kepercayaan dari pemerintah melalui surat keputusan dari Badan Akreditasi Nasional Perguruan Tinggi (BAN-PT) dengan peringkat akreditasi B (Baik).
Upaya ini selalu dipegang teguh oleh PS untuk selalu mengembangkan pendidikan tinggi melalui tri dharma perguruan tinggi yang selama ini dijalankan dengan baik, hingga akhirnya pada tahun 2016 Program Studi PAI kembali mendapatkan perpanjangan izin penyelenggaraan program studi. Pada tahun 2019 PS telah memiliki target untuk meningkatkan mutu dan kulitas pendidikan tinggi melalui tri dharma perguruan tinggi. Hal tersebut dilakukan agar kepercayaan dalam pengelolaan program studi yang selama ini diberikan oleh BAN-PT dapat meningkatkan peringkat akreditasi B (baik) menjadi peringkat akreditasi A (sangat baik).
Seiring dengan perbaikan di beberapa aspek di dalam tubuh Prodi PAI Fakultas Tarbiyah IAI Al-Qolam, mana prodi ini mendapat predikat B sesuai dengan SK BAN-PT No. 5332/SK/BAN-PT/Ak-PPJ/S/IX/2020.