Епископската базилика е најзначајниот христијански објект во Стоби. Се наоѓа западно од театарот и во нејзината егзистенција постојат два посебни периода. Првите ископувања биле во 1918 година, а истражувана е и во 1924 – 25, 1927, 1934, 1970 – 78, во текот на 80 – тите и во 90 – тите.

Првиот период се однесува на Старата Епископска Базилика, изградена во првата половина или средината на IV век, што ја прави најстара црква во Р. Македонија. Можеби ја подигнал епископот Будиос кој учествувал на првиот екуменски собор во Никеја во 325 година. Таа има трикорабна диспозиција при што средишниот кораб е одвоен со колонади од страничните. Некаде во втората половина на IV век црквата е проширена кон исток, а обновени се и северниот и јужниот ѕид. Подот има три зони на мозаик со геометриски мотиви. Во едно поле стои натпис дека епископот Евстатиј е обновителот. На северниот и јужниот ѕид од базиликата се сочувани фреските од IV век што е единствен случај во Македонија. На нив се забележуваат геометриски мотиви, но има и животински и светителски претстави.

Вториот период започнува во првата половина на V век со изградбата на новата монументална Епископска Базилика. Од еден натпис кој стоел над влезот во наосот на црквата, дознаваме дека ова се случило во времето на епископот Филип. Интересно е тоа што новите градители не ја срушиле комплетно старата црква туку подигнале високи темели и го насипале внатрешниот простор. Така, новата црква е издигната околу 4 метри над нивото од старата базилика со што доминира над околниот простор. Таа има два спрата, a во нејзината архитектура се употребени седишта и столбови од театарот со што максимално е изразена нејзината грандиозност.

Од улицата Via Sacra најпрвин се влегува во атриумот на базиликата, а оттука пак во нартексот кој е поделен на три дела со два пара на столбови. Подот на нартексот е украсен со мозаик на кој има геометриски мотиви и претстави на животни. На ѕидовите биле изведени фрески со ликови на светители. Нартексот комуницира со наосот и страничните простории на северната и јужната страна. Оттука преку скалила се стигнувало до крстилницата.

Централниот кораб бил одвоен од страничните со колонади чии столбови носеле прекрасни капители. Столбовите се поставени на стилобат од театарски седишта. Подот во овој кораб бил од мермерни плочи комбинирани со мозаик и сив шкрилец. Во источната половина се наоѓале проповедалницата и оградениот олтарен простор. Мермерните олтарни плочи од преградата имаат релјефно изведени крстови. Подот и олтарната преграда биле обновени. На источниот крај има двојна апсида при што во внатрешниот дел била сместена крипта, а на надворешниот ѕид имало прозорец со масивни сликани и позлатени капители.

Ѕидовите на северниот и јужниот кораб биле украсени со фрески. Јужниот кораб бил обновуван и има два мозаични пода еден над друг. Во постариот под била вкопана ѕидана гробница во која веројатно е погребан некој епископ. Јужниот ѕид на овој кораб е удвоен и во него, веднаш до крстилницата, има уште една гробница.

Крстилницата се наоѓа јужно од базиликата така што нејзиниот северeн ѕид е залепeн на обновениот ѕид од јужниот кораб. Има четирилистна форма впишана во квадрат и била покриена со купола. На средината има писцина со скали на две страни. Писцината била покриена со балдахин потпрен на мермерни столпчиња.  Подот во крстилницата е декориран со мозаици на кој се претставени пауни помеѓу кои има кантарос и елени помеѓу кои има канатарос. Ова е илустрација на Давидовиот псалм 42. Ѕидовите биле украсени со фрески со претставени светители. Од почетокот на VI век покрстувањето не се изведувало со потопување во писцината, туку за таа намена во употреба бил голем мермерен кантарос.

Според наодот на монета од 569 – 70 година под срушените ѕидови на црквата, можеме да констатираме дека базиликата го доживеала својот крај некаде после овие години.