Ιn the early 10^th century a small three-nave basilica was founded on the ruins of a Justinian cistern in the citadel of Rentina. To date only the wall foundations and fragments of the decorations have been studied. According to a citation in Novel 16 by Emperor Leo VI the Wise , the church was the seat of the Bishop of Lete and Rentina. Building remains that may have belonged to the episcopal residence were brought to light to the north-west of the church. Other finds include a one-storey storage magazine to the south-west, which housed the oldest covered water tank in the citadel.

Three tripartite arches projected from the east wall of the church. The largest central arch was dressed at a later date, probably for support. The naves were separated by arches supported on piers or a combination of piers and columns ; it also appears that the initial plan included galleries . The church walls were made of small stones and mud plastered on the outside. Several tombs have been excavated beneath the aisle floors and outside the church up to the north end of the citadel wall.

An earthquake provoked irreparable damage to the church in the 13th century, initially causing the wall paintings to collapse, followed over time by other parts of the church. However, burials continued inside the church until the roof collapsed completely, as is evident from 14^th century coins found both inside and outside the tombs.