The (old and new) Episcopal Basilica is located to the West of the Roman Theatre in the Roman and Early Byzantine city of Stobi and was discovered by the German Army in 1917/18. It is the most important Christian monument in Stobi and was built in two phases. In the first phase, the old Episcopal Basilica was built in the first half or the middle of the 4th century. It had three naves, and the side naves were separated from the main nave by columns. In the second half of the 4th century, this basilica was extended to the East (narthex). The floor features a mosaic with geometric motifs and an inscription in the naos, which testifies that Bishop Eustathios renovated the church. In addition, remains of 4th-century frescoes (with geometric motifs, depictions of Saints and animals) are preserved on the Northern and Southern walls. In the first half of the 5th century, the second phase of construction began with the erection of the new Episcopal Basilica. This is evidenced by a Greek inscription on a lintel above the entrance to the naos, which names a bishop Philippos as the builder.
The old Episcopal Basilica was not destroyed, but filled in and used as a substructure for the new Episcopal Basilica, so that the former lay up to 5 m below the latter. Benches and columns from the Roman Theatre (see above) were used in the construction of the new Episcopal Basilica. From the Via Sacra, one first entered the atrium of the basilica in the West, then the narthex (mosaic floor with geometric motifs and animal depictions, frescoes of Saints on the walls). The naos has three naves, with the main nave separated from the side naves by columns. It has a rich interior decoration (architectural sculptures in white marble, mosaic floors, marble floors, fresco remains, crypt in the apsis area).
Paul Clemen describes the archaeological endeavour by the German Army as follows: "Nur eine planmäßige größere Grabung ist während der Zeit der militärischen Besetzung unternommen worden. Im Gebiete der antiken Stadt Stobi hatten deutsche Offiziere von dem wichtigen Etappenort Gradsko aus Forschungen begonnen. Sie führten zur Entdeckung von drei Basiliken, deren eine, außerhalb der antiken Stadt in der Nähe von Palikura gelegen, fast ganz freigelegt, aufgeräumt und, infolge des lebhaften Interesses, das auch der Oberbefehlshaber, General-Feldmarschall von Mackensen, der Arbeit entgegenbrachte, soweit das unter solchen Verhältnissen möglich war, gegen Beschädigungen geschützt wurde. Die Fortsetzung der gleichfalls begonnenen Freilegung der beiden anderen Kirchen, die in der antiken Stadt gelegen sind, wurde von den bulgarischen militärischen Stellen gehindert. Als ich im Sommer 1917 nach Stobi kam, ergab sich mir, daß die auf halbem Wege steckengebliebene Arbeit kein wissenschaftliches Ergebnis zeitigen konnte, dagegen bei der unmittelbaren Nähe des großen Etappenortes die aufgedeckten Reste sicherer Zerstörung aussetzte, ehe sie wissenschaftlich verwertet werden konnten. Auf meine Verwendung bei Herrn Professor Filow fand sich die Direktion des Nationalmuseums in Sofia bereit, die Erlaubnis zur Aufdeckung bei den bulgarischen militärischen Stellen zu erwirken und diese zu vollenden, wozu die Landeskundliche Kommission Dr. Krischen zur Verfügung stellen konnte. Herr Krischen hat dann 1918, nachdem er zuvor schon die in der deutschen Etappenkommandantur aufbewahrten Fundstücke genau bearbeitet hatte, mit Unterstützung der bulgarischen Kommandantur in Gradsko, die eine Anzahl Soldaten zur Verfügung stellte, zunächst die große Begräbniskirche freigelegt, die wohl noch dem fünften Jahrhundert angehört. Die eingeschossige Basilika hatte einen prächtigen Mosaikboden, einen geometrisch geteilten und bis auf einige Felder mit Tierdarstellungen auch geometrisch geschmückten Teppich. Bei seinem ungünstigen Erhaltungszustande war an ein Fortschaffen oder an dauernde Erhaltung leider nicht zu denken. Doch sorgte militärische Bewachung für einstweiligen Schutz, bis eine genaue Aufnahme in großem Maßstab fertiggestellt war. Dann wurde in der großen Basilika inmitten der Stadt, die wohl zweigeschossig war wie S. Demetrius in Saloniki, weitergegraben und dort eine Fülle von Trümmern sehr schöner Marmorschranken mit durchbrochener Arbeit, Brocken von Stuckornamentik und Freskomalereien, Glasmosaiken und namentlich das oben S. 159 abgebildete prachtvolle Kapitell entdeckt. Alle diese fanden einstweilen in der deutschen Etappenkammandantur Gradsko Unterkunft, so daß hier allmählich ein kleines Museum entstand. Leider sind die zum Teil recht wertvollen Gegenstände dort vergebens geborgen worden und wahrscheinlich in der allgemeinen Katastrophe mit untergegangen."