Arap Camii’nin yapım tarihi ve kim tarafından yapıldığı tartışmalıdır. Cami duvarındaki kitabede inşaa tarihi 717 olarak görülmektedir. İstanbul kuşatması için buraya gelen “Mesleme bin Abdülmelik” komutasındaki ordunun buraya cami inşaa ettiği(yada buradaki bir katedrali camiye çevirdiği) Arap ordularının buradan gittikten sonra kiliseye çevrildiği fetihten sonra tekrar cami olduğu görüşlerden birisidir.( Arap ordusunun 150.000 kişi ve 1700 gemisini kaybettiği kuşatma ile ilgili Arap ve Bizans tarihi metinlerde kuşatma sırasında bir caminin yapıldığı geçer.)
Diğer bir görüş ise Wikipedia’da yer alan şu metindeki gibidir.
“Dördüncü Haçlı Seferi’nde Kudüs yerine Konstantinopolis’i ele geçirmeyi yeğleyen Katolikler, 1200’lerin başlarında Pavlus’a adadıkları bir kiliseyi ve yanına Dominiken Mezhebine bağlı bir manastırı Galata’da yaptırmışlardır. Papaların da yakın ilgisini çeken bu manastır ve kilise, bir süre sonra mezhebin kurucusu olan “San Domeniko”nun adının da eklenmesiyle tanınır: San Paolo ve San Domeniko1475’te Fatih, kiliseyi camiye çevirterek vakfına katmıştır. Yirmi yıl sonra da, İspanya’dan çıkartılan Endülüs Arapları’nın bir kısmının, çevredeki mahallelere yerleştirilmesiyle cami, “Arap Camii” olarak tanınır. Caminin Araplara mal edilmesinin bir nedeni de, minareye çevrilen eski çan kulesinin 714’te Şam’da yaptırılan ünlü Emeviye Camii’nin özgün minaresini çağrıştırmasıdır.”
Yukarıda belirtilen iki görüşten hangisinin doğru olduğu bilinmiyor.
3. Mehmet ve 1. Mahmut’un annesi Saliha Sultan ve 2. Mahmut’un kızı Adile Sultan değişik dönemlerde camiyi onartmış; hünkar mahfili, sebil, çeşme, şadırvan gibi ögeler ekletmişlerdir. Özellikle Saliha Sultan’ın yaptırdığı onarımdan sonra caminin iç düzeni, mahfillerin, mihrabın barok ahşap tasarımlarıyla hayli değişmiştir. 1913-1919 yılları arasındaki kapsamlı onarım sonucu yapı büyük bir değişime uğrar: Avlu duvarı yıkılır, Cami genişletilerek yeniden yaptırılır. Bu tamirat sırasında zeminden çıkan Ceneviz`lilere ait kitabeli ve armalı mezar taşları Arkeoloji Müzesi`ne taşınmıştır. Yine bu onarımlar sırasında mihrabın yanındaki “Mesleme’nin Çilehanesi”, “Arap Baba Merkadi” ve çevrede sahabelere ait oldukları düşünülen kabirler düzenlenmiştir.
Cami çevresinin iş yerleri ile çevrili olması yapıyı boğmuş etraftan görülmesini engellemiştir.