This is an Early Christian Basilica located to the south of the Civil Basilica. The name of the building stems from the fact that below the Basilica there are remains of two older Synagogues. The excavations of the complex were done in 1931 and 1970 – 74.

At the western end of the building there is an atrium (peristyle) entered from the street Via Principalis Inferior. To the east of the atrium there is a narthex and to the south there are couple of other rooms which communicate with the House of Polycharmos. The basilica has three aisles separated with colonnades. The floor of the basilica was made of tiles and sandstone slabs. In the altar there was a reliquary with a cross – shaped mouth. The basilica was built at the end of the 4^th or the beginning of the 5^th century AD.

The first excavations in 1931 uncovered an inscribed column which reveals the fact that Claudius Tiberius Polycharmos, father of the Synagogue in Stobi, donated parts of his house for the needs of the temple. The excavations in the ‘70s, below the floor of the basilica, resulted with the discovery of two synagogues built one above the other. Synagogue II was erected towards the end of the 3^rd or the beginning of the 4^th century AD while the older Synagogue I is from the 2^nd century AD. The walls of Synagogue I had inscriptions: dedicated to the Father Polycharmos. After the destruction of Synagogue I the new Synagogue II was built. It was a larger temple with mosaic floors of geometrical motifs. The mortar on one of the walls had an inscribed menorah. During the conservation activities in 1994 a round marble plate was discovered. The plate has an inscription which reveals that Alexander phrontistes (guardian, curator of the synagogue) rebuilt the porch of the synagogue at the end of the 3^rd or the beginning of the 4^th century AD.

Remains of a Hellenistic building and a coin hoard were discovered in the strata underneath the narthex of the basilica. The hoard contained coins from the period between 211 and 125 BC.