Sebelum tahun 1998, pejabat ini merupakan salah satu bahagian di Jabatan Agama Islam Wilayah Persekutuan (JAWI). Pada waktu itu, Mufti Wilayah Persekutuan sebagai ketua kepada bahagian yang dikenali sebagai “Bahagian Istinbat”.
Pada 1 Oktober 1998, bahagian tersebut telah diasingkan daripada struktur JAWI berikutan penyusunan semula struktur Jabatan Perkhidmatan Awam, Bahagian Pembangunan Operasi. Pada peringkat awal operasinya, pejabat ini hanya terdiri daripada 6 orang anggota sahaja.
Mulai tahun 2000, semua urusan pentadbiran dan kewangan pejabat diuruskan sepenuhnya oleh pejabat ini dengan mendapat waran peruntukan mengurus daripada Jabatan Perdana Menteri. Pada 3 Mac 2004, Pejabat Mufti Wilayah Persekutuan cawangan Labuan telah ditubuhkan. Pejabat Mufti cawangan Labuan beroperasi di Bangunan Ujana Kewangan Wilayah Persekutuan Labuan.
