Diasaskan pada tahun 1952 oleh Allahyarham Tuan Guru Haji Ahmad Bangkok (salah seorang anak Tok Kenali dan merupakan ulama terkenal negeri Kelantan) dengan nama Madrasaturrahman Al-Ahmadiah Kenali di kawasan pondok Tok Kenali sekarang.

Guru Besar yang pertama ialah Hajjah Rahmah Binti Haji Ahmad anak sulung kepada Tuan Guru Haji Ahmad Bangkok yang juga ibu kepada Pengerusi PIBG sekarang iaitu Profesor Dr. Wan Ahmad Kamil Bin Wan Abdullah.

Pada tahun 1963, ia beralih tempat ke tapak yang ada sekarang iaitu di atas sebuah tanah wakaf dan setelah mendapat bangunan baru (satu tingkat) sumbangan Kementerian Pembangunan Negara dan Luar Bandar. Bangunan ini dirasmikan oleh Yang Amat Berhormat Tunku Abdul Rahman Putra Al-Haj, Perdana Menteri Tanah Melayu pada 7 Jun 1963.

Rentetan kemunculan Sekolah Aneka Jurusan yang diperkenalkan oleh Kementerian Pendidikan Malaysia pada tahun 70-an,maka pada tahun 1973 Madrasaturrahmah antara sekolah rakyat yang terpaksa gulung tikar kerana tidak mendapat sambutan daripada masyarakat.

Pada tahun 1974 hingga 1983, bangunan sekolah ini telah diswastakan kepada Dato’ Haji Hassan Bin Harun dan diberi nama Akademik Kenali sebagai pusat pengajian berbayar.

Pada tahun 1974 juga, ahli jawatankuasa Madrasaturrahmah Kenali berusaha menghidupkan kembali fungsi sekolah agama di samping mengekalkan persekolahan swasta yang diusahakan oleh Akademik Kenali namun usahanya tidak berhasil.

Pada tahun 1989, setelah rundingan dan persetujuan dibuat maka Madrasaturrahmah Kenali diserahkan pentadbirannya kepada Yayasan Islam Kelantan (YIK) maka dari sini bermulalah ia sebagai sekolah bantuan separuh kerajaan dengan nama SMU (A) AR-RAHMAH KENALI.

Ustaz Haji Zainal Abidin Bin Muhd. Mahyuddin dilantik sebagai Pengetuanya yang pertama manakala jumlah pelajarnya yang mendaftar hanya 35 orang sahaja tetapi dengan berkat kesungguhan dan komitmen beliau, jumlah pelajar terus meningkat dari semasa ke semasa sehingga mencecah 1000 orang pada penghujung perkhidmatannya pada tahun 1999. Di samping itu, perubahan prasarana juga berlaku seperti perpustakaan dan bahan bacaan ditambah, kantin diperbesarkan, bilik guru dan kelas yang lebih selesa dan satu blok bangunan dua tingkat siap dibina.

Pada tahun 2000, Ustaz Haji Mohammed Zain Bin Abdul Rahman dilantik menjadi Pengetua menggantikan Ustaz Zainal Abidin. Pengalaman beliau sebagai Pengetua di Darul Anuar turut menyumbangkan pembangunan pesat dan kemajuan SMU (A) AR-RAHMAH KENALI. Sebuah bangunan asrama yang bernilai hampir setengah juta dan masjid dua tingkat bernilai hampir setengah juta berjaya dibina.

Pada tahun 2002, telah bermula satu cetusan bersama antara pentadbir sekolah dan Jawatankuasa Pembangunan Kemajuan Sekolah (JPKS) untuk mengusulkan supaya sekolah ini diserahkan sepenuhnya kepada Yayasan Islam Kelantan (YIK).

Pada 20 Ogos 2004, satu memorandum daripada JPKS kepada YAB Tuan Guru Dato’ Nik Abdul Aziz Bin Nik Mat, Menteri Besar Kerajaan Negeri Kelantan telah membuat permohonan menaiktaraf menjadi sekolah agama penuh kerajaan negeri.

Setelah rundingan dan perjumpaan dibuat menyusuli memorandum tersebut, maka pada Januari 2005 SMU (A) AR-RAHMAH KENALI secara rasmi menjadi sekolah Kerajaan Negeri Kelantan.