Kementerian Agama Kota Sabang merupakan salah satu instansi vertikal dari beberapa instansi yang ada saat ini di jajaran Pemerintah Daerah Kota Sabang. Cikal bakal Kementerian Agama Kota Sabang bermula sejak tahun 1963 dengan nama Jawatan Agama Kewedanaan Sabang. Saat itu yang menjadi Pimpinan Pertama Adalah Tgk.Razali Hasan. Beralamat dijalan Dipenogoro dengan menempati sebuah gedung peninggalan Belanda yang dipinjam pakai oleh Pemerintah Kota Sabang.
Pada tahun 1965 Sabang menjadi kotamadya yang sebelumnya merupakan kewedanaan Aceh Besar. Maka Kantor Kementerian Agama yang dikepalai oleh Tgk. Mahmud Krueng Kalee Saat itu berpidah alamat ke Jalan Dipenogoro, bekas gedung pertemuan / hiburan Belanda disamping kantor PDAM Sabang. Kemudian Pada Tahun 1967 ditetapkan Perwakilan Departemen Agama Kotamadya sabang yang dikepalai oleh Tgk.AR.Hasyim sampai dengan tahun 1973. Pada tahun 1973 Kepala Kantor Departemen Agama dipimpin oleh Drs. Said Salahuddin. Seiring pemekaran Kota Sabang pada tahun 1984, pada saat Walikota dipimpin oleh Drs. Yusuf Walad, MBA. dengan melakukan pembangunan Sabang secara besar-besaran. sebagian kantor dipindahkan ke lokasi yang baru yang bertempat dijalan KH. Agussalim Kelurahan Ie Meulee Sabang, tempat berdirinya Kantor Kementerian Agama sekarang. dengan kontruksi bangunan lantai satu sampai tahun 2001, namun pada tahun 2002 mendapat bantuan APBN, maka dibangunlah gedung berkontruksi dua lantai yang memiliki ruang yang memadai dan fasilitas pendukung yang hampir lengkap.