Bir rivayete göre , İstanbul’un Fethi için 717 yılında , Müslüman Arap kumandanlarından Mesleme bin Abdülmelik ordusu ile birlikte Hicri 95 Senesinde denizden kuvvetli bir donanmayla Bizans’ı kuşatmıştır. Kuşatma bir yıl sürer ama Konstantiniyye alınamamıştır. Fakat Galata fethedilmiştir. Mesleme Bin Abdülmelik ile İmparator Leon arasında yapılan anlaşma sonucunda Arap mescidi inşaa edilmiş ve ibadete açılmıştır. Konstantiniyye'de müslüman ordusu yedi yıl kalmış fakat yedi yıl sonunda Şam'da isyan çıkması üzerine , islam ordusu Konstantiniyye'den ayrılıp Şam'a gider bunun üzerine Dominiken Papaz ve Rahipleri Arap mescidini kiliseye çevirir. Osmanlı Ordusunun Konstantiniyye fethinden sonra tekrardan camiye çevrilir.
1913-1919 tarihleri arasında geniş kapsamlı onarım yapılmıştır. Camii genişletilmiştir. Mihrabın yanında bulunan "Mesleme'nin Çilehanesi", "Arap Baba Merkadi" ile sahabelere ait kabirin yerleri belli edilir.
