Kementerian Agama Republik Indonesia didirikan pada tanggal 3 Januari 1946 dengan nama Departemen Agama. Pembentukan Departemen Agama dalam Kabinet Sjahrir II ditetapkan dengan Penetapan Pemerintah No 1/S.D. tanggal 3 Januari 1946 (29 Muharram 1365 H) yang berbunyi; Presiden Republik Indonesia, Mengingat: usul Perdana Menteri dan Badan Pekerja Komite Nasional Pusat, memutuskan: Mengadakan Kementerian Agama.
Haji Mohammad Rasjidi diangkat oleh Presiden Soekarno sebagai Menteri Agama RI Pertama. H.M. Rasjidi adalah seorang ulama berlatar belakang pendidikan Islam modern dan di kemudian hari dikenal sebagai pemimpin Islam terkemuka dan tokoh Muhammadiyah. Sehari setelah pembentukan Departemen Agama, Menteri Agama H.M. Rasjidi dalam pidatonya yang disiarkan oleh RRI Yogyakarta menegaskan bahwa berdirinya Departemen Agama adalah untuk memelihara dan menjamin kepentingan agama serta pemeluk-pemeluknya.
Berdasarkan Peraturan Presiden No. 47 Tahun 2009 tentang Pembentukan dan Organisasi Kementerian Negara serta Peraturan Menteri Agama No. 1 Tahun 2010 tentang Perubahan Penyebutan Departemen Agama Menjadi Kementerian Agama, maka Departemen Agama berubah nama menjadi Kementerian Agama.
Kementerian Agama Kabupaten Pemalang sejak pertama kali dibentuk telah beberapa kali mengalami pergantian pemimpin / kepala, antara lain :
- K.H. Argubi, periode : -;
- Mahzun, periode : -;
- H. Faqihudin, periode : 1967 – 1975;
- Drs. Muanas Abdul Jalil, periode : 1975 – 1980;
- Prisan Hadi, periode : 1980 – 1989;
- H.A. Thosir, periode : 1989 – 1995;
- Drs. H. Hadjam Zakaria, periode : 1995 – 2000;
- Drs. H. Wahyadi A. Ghani, M.M., periode : 2000 – 2003;
- H. Muala Hata, S.H., periode : November 2003 – Mei 2007;
- Drs. H. Masduki, M.Si., periode : Mei 2007 – April 2010;
- Drs. H. Muslim Umar, M.Ag. periode : Agustus 2010 – Desember 2014;
- H. Taufik Rahman, S.H., M.Hum., periode : Desember 2014 – Maret 2019;
- Drs. H. Kudaifah, M.Pd.I., periode : Maret 2019 – Oktober 2019;
