It lies at the end of the valley which divides the fourth and fifth hills of Constantinople and overlooks the Golden Horn from its imposing position .

It is sometimes identified with the church belonging to the nunnery of Saint Theodosia (Greek: Μονή τής Άγιας Θεοδοσίας εν τοις Δεξιοκράτους, Monē tis Hagias Theodosias en tois Dexiokratous) or with that of the monastery of Christ the Benefactor (Greek: Μονή του Χριστού του Ευεργέτου, Monē tou Christou tou Euergetou).

[2] After Stephan Gerlach visited it in the late 15th century, the building was always identified as the church of Hagia Theodosia en tois Dexiokratous.

However, at the beginning of the last century, Jules Pargoire identified it instead as the church of Hagia Euphēmia en tō Petriō, built during the reign of Basil I (867–886), and explained why he thought this was the case.

[3][4] He refuted the idea that the Gül Mosque was the building where the body of Hagia Theodosia was brought at the end of the Iconoclasm period.

[6] On January 19, 729, at the very beginning of the iconoclastic persecutions, Emperor Leo III the Isaurian ordered the removal of an image of Christ which stood over the Chalkē, the main gate of the Great Palace of Constantinople.

[7][8] While an officer was executing the order, a group of women gathered to prevent the operation, and one of them, a nun named Theodosia, caused him to fall from the ladder.

[9] After the end of the Iconoclasm era, Theodosia was recognized as a martyr and saint, and her body was kept and worshiped in the church of Hagia Euphemia en tō Petriō, in the quarter named Dexiokratiana, after the houses owned here by one Dexiokrates.

[3] On April 12, 1204, during the Fourth Crusade, the Latin fleet gathered in front of the monastery of Christos Euergetes before attacking the city.

On that day, which was the eve both of the saint's feast and also of the end of the Byzantine Empire, the Emperor Constantine XI went with the Patriarch to pray in the church, which was adorned with garlands of roses.

After entering the city, the Ottoman troops arrived to find the building still adorned with flowers, hence, it is thought to have been called "Rose Mosque".

[15] Between 1573 and 1578, during his sojourn in Istanbul, the German preacher Stephan Gerlach visited the mosque and identified it with the church of Hagia Theodosia.

Eventually Sultan Murad IV restored it, rebuilding the dome and its pendentives, almost the whole west side, the vaults at the southwest and northwest corners, and the minaret.

A tradition that one of the piers hides the burial place of the last Byzantine Emperor only dates back to the nineteenth century, and is groundless.