The building's Byzantine origins are uncertain in the most interesting way: scholars have proposed multiple identifications without any of them being conclusively proven. The site on the sixth hill, bounded by the ancient cistern of Aetius to one side and the remains of a structure called Bağdan Saray on the other, was a place of monasteries and nunneries during the middle Byzantine period. The Monastery of Manuel lay nearby. The Kecharitomene nunnery — whose name means "full of grace" — occupied the area, and its typikon mentions two adjacent churches, the Theotokos tes Kellararias and the Hagios Nikolaos, as potential candidates for the structure that would become the Odalar Mosque. A church dedicated to Saints Sergius and Bacchus, described in sources as lying "near the cistern of Aetios," is another possibility. What is known is that a church stood here and was rebuilt: between 1150 and 1175, a new church in the cross-in-square plan was constructed above the older one, which may have been destroyed by fire.

The documented history of the building begins in 1475, when Sultan Mehmed II conquered Caffa, the Genoese colony on the Crimean coast. Around 40,000 people — Latin, Greek, Armenian, and Jewish inhabitants of Caffa, known as Caffariotes or, in Turkish, Kefeli — were uprooted and transported to Istanbul. This was a forced displacement of an entire multi-ethnic port community, people who had no say in where they were being sent or what would be asked of them when they arrived. They were settled in this part of the city, which was renamed Kefe Mahallesi after them. The Genoese Catholics among the deportees were permitted to use the old Byzantine church as their chapel. They brought with them a large icon of the Hodegetria type from Caffa, a devotional object that had made the journey with the community. For over a century and a half, this building served the displaced people of Caffa as a place of Christian worship in an Ottoman city.

In 1636, following riots between the Christian and Muslim communities of the neighborhood, the church was closed to Christian use. Four years later, in 1640, Grand Vizier Kemankeş Mustafa Pasha had it converted into a mosque, which took his name. The Hodegetria icon was moved to Galata with difficulty — it is now kept in the Dominican monastery of Saints Peter and Paul there. A bishop named Pietro Demarchis, from Santorini, had visited the building in 1622 and left a record of what he saw: the original stone columns had already been removed and replaced with wooden pillars; the dome was covered in frescoes. His account captures the church in its last decades of Christian use, already somewhat altered, already being slowly changed by the pressures of its situation.

The older Byzantine church sat on a basement of twenty-four vaulted rooms, with a vaulted crypt and an apse that may have contained relics. The twelfth-century church built above it used sixteen of those basement rooms as its own substructure, and the floor of the newer building sat 3.3 meters above the older one. When archaeologists eventually investigated, they found something extraordinary below: Byzantine frescoes of the tenth and eleventh centuries, belonging to the first church. Among them was a representation of the soldier-saint Mercurius, described as being of unparalleled technique among known Byzantine works of the period. There was also a deesis composition, and prophets. The frescoes of the twelfth-century church's diakonikon showed saints and episodes from the Life of the Virgin. The best-preserved paintings, including the Saint Mercurius, were detached, conserved, and placed in the Istanbul Archaeology Museum, where they can be seen today — the most lasting thing to have survived from a building that has otherwise largely disappeared.