The church is located 120 meters to the southwest of the City Wall. This is the reason why it is called “Basilica outside the walls”. It was discovered in 1992 and there were couple of excavation campaigns until 2001.
The Extra Muros Basilica is the second largest church in Stobi. It has three aisles and a narthex. The aisles are separated by colonnades and some of the columns and capitals belong to older buildings. The central nave has a mosaic floor with rectangular zones. In the zones there are various depictions of Early – Christian motifs.
At the south side of the basilica there are three rooms. The central room is the baptistery with a circular piscina.
The basilica was built in the context of the suburbia of Stobi from the end of the 5th and the 6th century AD.
During the Middle Ages, a small church of modest architecture was built inside the altar of the ruined basilica.