The church was originally dedicated to the Theotokos Kyriotissa. The building represented one of the few exiting examples of a Byzantine church with a domed Greek cross plan.
The first building on this site was a Roman bath, followed by a sixth-century hall church with an apse laying up against the Valens Aqueduct. Later – possibly in the seventh century – a much larger church was built to the south of the first church. A third church, which reused the sanctuary and the apse of the second one, can be dated to the end of the twelfth century during the late Comnenian period.
After the conquest of Constantinople in 1453, the church was assigned personally by Mehmed II to the Kalenderi sect of the Dervish. The Dervishes used it as a zaviye and imaret (public kitchen), and the building has been known since as Kalenderhane.
- Kalenderhane translates as "home of the kalenderi", whereas camii means "mosque".