The church of Agios Stefanos lies on a hill on the northeast part of Kastoria. Dating the monument is problematic as there is no information from inscriptions or other sources. However, based on the church’s oldest surviving wall paintings, construction took place in the early 10th century.
From an architectural point of view, the church is three nave barrel-vaulted basilica with a narthex and a higher central nave . The side naves are connected by two symmetrical arcs, while blind arches, two on each side, adorn the walls of the side naves. The three naves and the narthex are covered with semi cylindrical arches. The sanctuary conch is semi-hexagonal externally and has a built synthronon on the inside. Three arched openings allow all aisles to communicate with the narthex, which occupies the entire width of the church, while a built staircase on the north side leads to the upper floor. On the south part of the upper floor there is a chapel dedicated to Agia Anna, while an arched window opens to the nave. The gallery , unique in the Byzantine churches of Kastoria, is mentioned in local tradition as a hermitage.
The exterior of the church has a rich ceramic decoration. The masonry is made of irregular stones in bands defined by double rows of bricks while other bricks placed vertically or diagonally between the stones create a variety of shapes, common to several of the city’s Byzantine churches. The church is illuminated by narrow single-light , arched windows, which are surrounded by a single row of bricks either entirely, or just around the lobe of the window. The three single-light apse windows are crowned by dogtooth courses that run across the apse. A frieze extended to the dogtooth cornice is decorated with simple ceramic tiles. Similar decoration adorns the central aisle pediment and a frieze on the highest point of the sides defined by dogtooth courses. Two "suns" similar to those of Agioi Anargyroi and the Archangel of the Gymnasium, adorn the east side of the raised aisle. The main church entrance is on the west side but, since the opening up of the north wall door, it is hardly ever used today. The main south wall entrance of the church is now secondarily used.
The interior painted decoration of the church is rich. The first painted layer, which once covered all the surfaces, was created just after the monument was erected and can be dated to the early 10th century. One of the most characteristic and best preserved representations of the first layer is the Second Coming in the narthex . It is a big composition, the oldest in mainland Greece, covering the vault and the narthex walls and extends on the side walls of the upper floor staircase. The figures of the apostles and angels, represented in normal proportions, tranquil and displaying restrained movement, are laid out symmetrically along a band running across the narthex.
The second layer iconographic program, dating to the early 13th century, is divided into three zones, with evangelical scenes, prophets and the three ages of Christ in the nave arch. The main feature of the scenes is their size, the simple and highly structured composition with few, tall graceful figures. Stylistically they follow the academic painting tradition with the standardized elements of the 12th century, influenced by the late-nomnenon style.
From the 13th up until the 14th century a number of individual representations were painted in various parts of the church by different donators. The portrait of Father Theodore Lemnos (late 13th - early 14th century) offering a model of the church to Agios Stephanos stands out; also worth mentioning is the depiction of the "petty supplicant George" below the representation of Mary Gorgoepikoos. The many devotional representations, the burial use of the church, the existence of the synthronon -chair and the hermitage lead to the assumption that this was probably a monastic church.