Sekolah Menengah Agama Kampung Gajah (SEMEGAH) telah mula beroperasi pada tanggal 14 April 2000 dengan pelajar perintisnya seramai 200 orang. Ia merupakan sekolah berasrama penuh yang ketiga didirikan di daerah Perak Tengah selepas SM Teknik Seri Iskandar dan SMKA Sultan Azlan Shah, Bota.

Sekolah ini dibawah pentadbiran Jabatan Agama Islam Perak (JAIPk). Penubuhan sekolah ini telah diilhamkan oleh YAB Tan Sri DiRaja (Dr) Haji Ramli bin Ngah Talib, semasa beliau memegang jawatan Menteri Besar Perak. Letaknya kira-kira 3.5km dari pekan Kampung Gajah. Pembinaannya telah bermula pada tahun 1998 hingga tahun 2000 di atas tapak seluas 47 Ekar dengan kos bernilai RM18.4 Juta.

Sepanjang kewujudannya di Perak Tengah, ianya telah menunjukkan tahap pencapaian yang gemilang. Sekolah ini sentiasa dicemburui dan disegani kerana sering mendapat tempat dalam pertandingan yang disertai. Ia memberi saingan hebat kepada sekolah-sekolah lain milik Kementerian Pendidikan di Perak Tengah dalam bidang akademik mahupun kegiatan kokurikulum.[perlu rujukan]

Ini terbukti apabila buat pertama kali pada tahun 2002, kumpulan pelajar sulungnya telah membuat kejutan terhadap dunia pendidikan di Perak Tengah. Berjaya mendapat tempat kedua dalam peperiksaan Penilaian Menengah Rendah (PMR) dengan peratus keseluruhan 81.4%.

Sering sahaja memberi saingan hebat dalam beberapa pertandingan seperti badminton, ping pong, tenis, olahraga, bola sepak, kawad kaki, nasyid, tahfiz, dan tilawah al-Quran. Ketika Ulangtahun Sambutan Kemerdekaan Negara Ke-46 di Bota pada 1 September 2003, sekolah ini telah mencipta rekod peribadi apabila ketiga-tiga pasukan kawad kaki yang mengambil bahagian memperolehi kemenangan masing-masing. Dua pasukan puteri berjaya menjadi Johan bagi kategori Pasukan Sekolah dan Unit Beruniform, sementara pasukan putera pula mendapat tempat ketiga bagi kategori Pasukan Sekolah.

Setelah 4 tahun beroperasi, pada tanggal 9 Ogos 2003 bersamaan 11 Jamadil Akhir 1424H, sekolah ini telah disempurnakan perasmiannya oleh DYTM Raja Muda Perak Darul Ridzuan, Raja Dr. Nazrin Shah Ibni Sultan Azlan Muhibuddin Shah. Namanya berubah menjadi Sekolah Menengah Raja Dr. Nazrin Shah dengan singkatan sebagai SARJANA.

Nama sekolah ini diperoleh daripada pertandingan mencipta logo oleh pelajar-pelajar Sekolah Menengah Agama Kerajaan Negeri Perak. Lebih daripada 20 orang pelajar telah mengambil bahagian. Logo-logo yang terpilih kemudiannya dibawa ke mesyuarat pentadbiran JAIPk bagi memilih logo yang sesuai untuk dinobatkan sebagai juara secara automatiknya digunakan sebagai logo sekolah ini. Singkatan nama SARJANA telah dipersetujui oleh semua pihak untuk diguna kerana berdasarkan nama sekolah ini yang baru iaitu :-[perlu rujukan]

SA - Sekolah Menengah

RJA - Raja Dr

NA - Nazrin Shah

Perkataan ini juga mempunyai maksud yang tersendiri, sebagai bayangan terhadap matlamat dan cita-cita sekolah ini diwujudkan. Merujuk kepada Kamus Dewan, maksudnya adalah orang yang bijak pandai, berilmu pengetahuan, cendekiawan atau keahlian.

Ust. Mohd Darwis Bin Hj. Zakaria merupakan Pengetua yang pertama sekolah ini iaitu dari tahun 2000 hingga 2001. Pada tahun 2001 hingga tahun 2016 sekolah ini diambil alih pentadbirannya oleh Tuan Haji Omar Bin Bakar sebagai Pengetua.

Tiga pelajarnya berjaya mencipta mesin Pembakar Lemang Bersistem atau ITQUN AXY040 [2]Tiga pelajar tersebut ialah Muhammad Alif Ahmad Kamal, Mohamad Izharuddin Abd Halim dan Mohd Alias Hazwan Mohamad Hassan. Mesin itu berjaya meraih Anugerah Khas Projek Terbaik Intel Technologies Sdn Bhd pada Karnival Pendidikan Sains dan Teknologi Kebangsaan 2005 di Pulau Pinang pada 25 Ogos 2005. Guru pembimbing mereka ialah Fauziah Zainuddin dan Fadzilah Salleh.