The impressive Byzantine church of Panagia Odigitria, which after the 1821 Revolution of was renamed Agia Sophia, is built on the castle of Monemvasia, on a cliff above the sea.

Tradition relates the church to the Emperor Andronicus II Palaeologus, but sources reveal that the church, which was originally dedicated to the Virgin Hodegetria, is much older and dates to the mid 12th century, in 1150. The church continued to officiate during the first Venetian period (1463-1540) when it was known as Madonna del Castello or Nostra Donna in Castello for the Catholic officials. In the period of the first Ottoman rule (1540-1690) the church became a mosque with the addition of the mihrab , which is preserved by the south wall. During the second Venetian occupation (1690-1715) it was the Catholicon of a Western doctrine monastery and was dedicated to Madonna Del Carmine. During this phase a two storey Porch was added to temple across the width of the western side. The church functioned as a mosque again in the period of second Ottoman rule (1715-1821) and returned to Christian worship after the liberation of the city; it was then dedicated to Wisdom of God because it was an exact copy of the Agia Sophia of Constantinople. Subsequent dates 1827 and 1845 seen on the west side apparently correspond to repair works curried out on the building.

The church is a mainland octagonal church , like those of Daphni, Saint Luke, and Saint Theodore of Mystras, etc., dated to the mid 12th century (1150). To the west of the temple there is a narthex , which in earlier times stood two storeys tall; during the second Venetian rule an exonarthex was also added. Outside of the church and to the south, a double gallery of unknown function but lavishly built was added, which collapsed in 1893. The church is built of the cloisonné masonry and the three-light windows of the facets are decorated with ceramoplastic motifs .

The church preserves rich sculptural decoration, but due to the many irreversible modifications it sustained over the course of its long history, it was not possible to be repositioned in its entirety, and some parts are now in the Archaeological Collection of Monemvasia.

The painted decoration, which is only fragmentarily preserved, is of high quality and dates to the 12th or early 13th century. The surviving parts depict Christ with angels at the entrance leading from the narthex to the nave, saints, martyrs, bishops, Christ on a medal as the Old Days in the sanctuary, scenes from the life of St. Nicholas, etc.