The dedication to S. Theodore is based upon the identification of the surroundings with the Byzantine neighborhood of ta Karbounaria (the coal market),[5] but this is not sure.

Shortly after the Ottoman conquest of Constantinople, the church became a mosque, founded by the famous Kurdish scholar Molla Gürâni,[8] who was the tutor of Sultan Mehmed II and would become Şeyhülislam[7] and the first Mufti of Istanbul.

[10][11] The church proper, which has never been studied systematically,[3] has a cross-in-square (or quincunx) plan, with each side nine meters long.

Besides this building, the complex contains also an exonarthex to the west, a portico (which joins a parekklesion[14] with the bema) with columns and arches to the south, and finally a corridor to the north.

The exonarthex represents one of the most typical examples of Palaiologan architecture in Constantinople,[15] along with the parekklesia of the Pammakaristos, the Chora Churches, and Fethiye Mosque.

The internal decoration of the exonarthex includes: columns, capitals and closure slabs which are all reused material from the Early Byzantine period.

Those on the south and the central domes were cleaned in 1937 under the direction of M. I. Nomides and the Ministry of Mosques,[2][3] but as of 2007 they have disappeared almost completely.

[2] Two fairly large underground cisterns placed to the S and W of the church hint to the existence of a monastery in the Byzantine age.