The story begins in the early fifth century, when Princess Arcadia, sister of Emperor Theodosius II (r. 408–450), ordered the construction of a monastery near the Gate of Saturninus, about 600 meters west of the gate, on the slopes of the seventh hill above the Sea of Marmara. The monastery was called Rodophylion — "guardian of roses" — and was initially dedicated to Saint Andrew the Apostle.

By the late eighth century it had been converted into a nunnery. The martyred Andrew of Crete was buried here after 766, and the monastery's dedication shifted to him: it became known as Saint Andrew in Krisei — "in the Judgment," after the place where it stood, which bore the name hē Krisis, "the Judgment." Emperor Basil I (r. 867–886) wholly rebuilt the church in the second half of the ninth century, possibly repairing damage from the iconoclastic conflicts that had shaken Constantinople for generations.

In 1284, Princess Theodora Raoulaina — niece of Emperor Michael VIII Palaiologos and wife of the court official John Raoul Petraliphas — rebuilt the monastery and church again, earning the title of second ktētorissa, second founder. She spent the last fifteen years of her life within these walls and was buried here. When the Latin crusaders occupied Constantinople, the monastery fell into neglect. By the early 15th century the surrounding area had filled with vineyards — a telling sign of how far the once-proud city had declined.

Even in its diminished state, the monastery retained spiritual power. Two Russian pilgrims who visited Constantinople — one in 1350, another between 1425 and 1450 — recorded that Saint Andrew was still venerated here by people who came sick and hoping for healing. The church remained a place of pilgrimage even as the city around it contracted, the population shrank, and vineyards replaced houses on the surrounding slopes.

In 1427, Emperor John VIII Palaiologos (r. 1425–1448) ordered repairs to the harbor nearby, and contemporary records mention the monastery in passing. The Spanish traveler Pedro Tafur, who visited Constantinople in 1437, left a description of the area. The monastery survived to the very end of Byzantine rule. When Constantinople fell to Ottoman forces on 29 May 1453, the monastery was still standing — known by the Turks, who took it as a sign of its former function, as Kızlar Kilisesi: "women's church."

After the conquest, the monastery continued to be inhabited for a time. Between 1486 and 1491, Koca Mustafa Pasha — who served as kapıcıbaşı (head gatekeeper) and later rose to become Grand Vizier — converted the church into a mosque. He was executed in 1512, a casualty of court politics under Selim I. But his conversion of the building stuck, and the mosque bears his name.

Some years later, his son-in-law Şeyh Çelebi Efendi endowed the former monastery buildings as a tekke — a lodge — for dervishes of the Halveti order. The complex grew. At the beginning of the 17th century, the treasury minister Ekmekçizade Ahmet Paşa added a medrese, new gates, a zaviye, and a mekteb (school). About a century later, the Sultan's chief physician Giridli Nuh Efendi closed the tekke and enlarged the medrese. The building was restored again in 1953.

Folk memory attached itself to the mosque in the form of stories. A dead cypress tree still hangs with a chain once used — folk tales say — as a kind of lie detector. Tales of the çifte Sultanlar, the "twin Sultans," circulate with Byzantine roots. Scholars see in these stories the long process by which Ottoman and Greek popular culture merged over centuries of shared urban life.

The building began as an ambulatory church — a type where the central space is surrounded by walking aisles — oriented roughly east-northeast to west-southwest. It had a central dome, three apses on the east side, and double narthexes on the west. After the 1766 Istanbul earthquake destroyed the central dome, it was rebuilt: circular inside, octagonal outside, resting on a drum pierced by eight windows. The Ottomans added two half-domes on the north and south sides of the main dome, both pierced by large windows that look from outside like dormers.

The outer narthex, divided into five bays, retains Ionic capitals that resemble those used in the nearby Church of Saints Sergius and Bacchus — Little Hagia Sophia — suggesting they may share craftsmen or at least a shared design vocabulary. The exterior is plainly Ottoman: dressed stone, no tiles, molded cornices. The underground cistern southeast of the mosque is all that remains of the Byzantine monastery itself. A carved Byzantine door frame, possibly sixth century, was removed to the Istanbul Archaeology Museum. Despite its layers of history and its architectural complexity, the building has never received a systematic scholarly study. It waits.