The Cemetery Basilica is located about 250 m to the South-West of the Porta Heraclea (the main gate of the Roman and Early Byzantine city of Stobi). The basilica was discovered by the German Army in 1917/18 and has three naves with a narthex in the West. The main nave has a mosaic floor with geometric motifs (first half of the 5th century). The cemetery basilica was built in the 4th/5th century on a Late Roman necropolis and had a crypt (martyrium) on the Southern side. The cemetery is called the "Western Necropolis" (Zapadni Grobišta, graves from the 2nd century BC to the 6th century).
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."