Most scholars date the original Pammakaristos Church to the 11th or 12th century, with some attributing it to the reign of Michael VII Ducas between 1071 and 1078. The Swiss Byzantinist Ernest Mamboury proposed an earlier foundation in the 8th century, though this view remains a minority position. What is certain is that the building grew. Sometime after 1310, a noblewoman named Martha Glabas commissioned a small parekklesion — a side chapel — on the church's south side, as a memorial for her husband, the military commander Michael Doukas Glabas Tarchaneiote, who had served under the Emperor Andronikos II Palaiologos. The poet Manuel Philes wrote the dedicatory inscription that runs along the chapel's interior and exterior walls. This small addition, built with the cross-in-square plan under five domes, became one of the finest pieces of late Byzantine architecture in the city.

After the Ottoman conquest of 1453, the main church remained in Christian hands and took on new significance. The Ecumenical Patriarchate — the leadership of Eastern Orthodox Christianity — relocated to the Pammakaristos, making it the patriarchal seat for more than a century. A synod convened here in 1484, in which the council of Ferrara-Florence was formally condemned, a decision that defined the Orthodox Church's relationship to Rome for generations. The building was the last pre-Ottoman structure to serve as the patriarchal headquarters — a piece of Byzantine continuity holding on inside an Ottoman city.

In 1591, Sultan Murad III ordered the church converted into a mosque and renamed it Fethiye Camii — 'Mosque of the Conquest' — in honor of his military campaigns against Georgia and Azerbaijan. The transformation required significant interior changes. The arcades separating the nave from its side aisles were removed to open up the prayer space. The three original apses were demolished and replaced by a great domed room, set at an oblique angle to the original building's orientation. What had been carefully arranged as a Christian liturgical space was reconfigured for Islamic prayer, and the Patriarchate moved on. The conversion did not erase the parekklesion, however. That small chapel, separated from the main structure, retained its mosaics.

After years of neglect, the parekklesion was restored in 1949 by the Byzantine Institute of America and Dumbarton Oaks. A second, more comprehensive restoration began in 2021 and was completed in 2024. Today the side chapel functions as a museum, open to visitors, while the main building continues as an active mosque. The mosaics in the parekklesion remain the third-largest collection of Byzantine mosaic art in Istanbul, after the Hagia Sophia and the Chora Church. In the apse, Christ Hyperagathos appears with the Virgin Mary and John the Baptist. A complete Baptism of Christ survives to the right of the dome. The gold ground that surrounds every figure catches whatever light enters the chapel and gives it back transformed.