Masjid Agung Al Ma’Arif Kota Tarakan Provinsi Kalimantan Utara didirikan pertama kali oleh masyarakat Tidung yang berada di Kampung Selumid Kecamatan Tarakan Kabupaten Bulongan Provinsi Kalimantan Timur pada tahun 1961. Lokasi masjid terletak di Kelurahan Selumit Kecamatan Tarakan Tengah Kota Tarakan Provinsi Kalimantan Utara. Tepatnya berada di sisi salahsatu jalan utama di kota Tarakan, yaitu Jalan Yos Sudarso dan Jalan K.H. Agus Salim.
Menurut tokoh masyarakat Tidung pada masa itu, nama masjid diambil dari kata Al Ma’Arif yang memiliki arti pengetahuan dalam bahasa Arab. Ini mencerminkan peran masjid sebagai tempat untuk mendalami pengetahuan Agama Islam dan pengetahuan sosial lainnya. Kata Al Ma’Arif bentuk jamak dari kata ma’rifah dan derivasi dari kata ‘arafah berarti mengenal. Makna kata ini mencakup segala yang dikenal, baik dalam konteks agama, sains, maupun adat kebiasaan yang hidup di tengah masyarakat baik dalam skala lokal maupun skala global. Bangunan Masjid Al Ma’Arif awalnya hanya berupa konstruksi kayu non permanen dengan bentuk konstruksi bangunan panggung sesuai jenis konstruksi bangunan pada masa itu. Pada awal tahun 70an, bangunan Masjid Al Ma’Arif ditingkatkan konstruksinya menjadi bangunan semi permanen dan mengalami perluasan areal ibadah dalam masjid. Pada tahun 80an, kontruksi Masjid Al Ma’Arif ditingkatkan lagi luasan bangunannya, dan penambahan fasilitas seperti pembangunan menara yang pada masa itu menjadi salahsatu ikonik kota Tarakan.
Seiring perjalanan waktu dan pertambahan penduduk serta jama’ah, pada pertengahan tahun 1996 dimulai perubahan besar konstruksi bangunan Masjid Al Ma’Arif. Bangunan lama dibongkar secara keseluruhan, kemudian dimulai pembangunan konstruksi baru Masjid Al Ma’Arif. Proses pembongkaran masjid lama dimulai tanggal 13 Agustus 1996, secara simultan juga dimulai pembangunan konstruksi baru.
Mengawali pembangunan konstruksi baru masjid Al Ma’Arif, pada awal Tahun 1996 dibentuk Panitia Pembangunan Masjid Al Ma’Arif yang dipimpin langsung oleh Ketua Takmir Masjid Al Ma’Arif Bapak H. Joesoef Abdullah, SH. Pada saat itu, H. Joesoef Abdullah, SH., sedang menjabat sebagai Sekretaris Kota Administratif Tarakan. Kemudian Panitia Pembangunan Masjid Al Ma’Arif didukung oleh beberapa pengusaha sukses kota Tarakan, seperti H. Muhidin, H. Soefyantan, H. Abdul Khair, SE. (Hotel Taufik), dan H. Ahmad Sunadi, SE (Hotel Harmonis). Tokoh masyarakat lain yang terlibat diantaranya Imam Besar Masjid Al Ma’Arif H.M. Saat Selayung H. Husin, Ali Wasbar Thalib, dr. Aboebakar, M.Ph., Drs. Hasyim AK. H.M. Idris, H. Arsyad HA., H. Padlan Hamid, dan beberapa tokoh masyarakat lainnya.
Desain Masjid Al Ma’Arif dirancang oleh arsitek Ir. Ramli Alex, dengan konsep arsitektur dan konstruksi beton yang diharmonisasikan dengan kearifan lokal masyarakat Tidung, yang tergambar dalam bentuk jendela-jendela lebar dengan bukaan kesamping kanan-kiri. Desain struktur dipimpin langsung oleh Ir. Sofian (waktu itu Kepala Suku Dinas Pekerjaan Umum Kota Administratif Tarakan) dengan tim teknis terdiri dari pegawai Suku Dinas Pekerjaan Umum Kota Administratif Tarakan (Ir. Imbransyah AS, Ir. Jamaludin HS dan Syahrun). Bertindak sebagai kontraktor adalah PT. Indo Utama Karya yang merupakan perusahaan konstruksi milik H. Muhidin, yang dikenal juga sebagai pengusaha sukses dalam bidang perikanan.
