Tot i que no es coneix documentació d’aquesta època, moltes són les evidències que apunten a un antic lloc de culte en aquesta zona de la ciutat. La memòria dels sants màrtirs Just i Pastor la podria haver portada a Barcelona Paulí de Nola (Bordeus 355-Nola 431) durant la seva estada a la ciutat. És conegut que aquest senador romà va ser ordenat prevere la nit de Nadal de l’any 393 com a resultat de l’aclamació del poble barceloní. Paulí havia arribat a Barcelona després d’enterrar el seu fill Cels a Alcalá de Henares (Còmplutum) on havia mort vuit dies després d’haver nascut. Paulí explica que havia tingut el goig d’enterrar-lo a Còmplutum vora el lloc del martiri dels dos infants, Just i Pastor, màrtirs en aquesta ciutat durant la persecució de Dioclecià (any 305). Doncs bé, Paulí de Nola hauria portat la memòria i les relíquies dels infants màrtirs com a homenatge i record del petit Cels. Així, hauria influït en la cristianització d’un espai que per la seva proximitat al fòrum i el seu emplaçament dalt d’un turonet, podria haver tingut un ús cívic (lloc de culte romà, administració i/o distribució del sistema urbà de les aigües). Les restes arqueològiques recentment descobertes posen de manifest l’existència d’estructures monumentals romanes dels segles I-II dC i d’un complex episcopal actiu durant l’època visigòtica. En concret fins ara s’han trobat la base i el fust d’una columna romana reutilitzada que sembla pertànyer a una basílica visigòtica del segle VI, i una part d’una pica baptismal de la mateixa època. Així, doncs, a Sant Just, com a la Catedral, hi hauria hagut un culte cristià ininterromput des del segle IV.

De l’època visigòtica també es conserven dos capitells, reutilitzats posteriorment com a piques d’aigua beneïda que devien pertànyer a la basílica esmentada o al seu baptisteri. La identificació de la pica baptismal, que tenia molt probablement forma de creu i de dimensions semblants a la que s’ha trobat al subsòl de la catedral, confirma que la basílica va exercir funcions episcopals. Es tractaria, probablement, de la seu del bisbe catòlic de Barcelona durant el temps en què la catedral hauria estat en mans del bisbe arrià (els visigots eren arrians, mentre que els hispanoromans eren catòlics). També és probable l’ús de la basílica de Sant Just com a seu episcopal durant el període musulmà, del 718 al 801, quan una part de la catedral hauria estat utilitzada com a mesquita. L’existència de dos baptisteris en una mateixa ciutat és un fet molt inusual durant el període tardoromà (tan sols es coneixen els casos de Ravenna i Barcelona), ja que el baptisme era administrat només pel bisbe la nit de Pasqua i a la seva església catedral.
La conquesta carolíngia (any 801) de la ciutat donà lloc a la reinstauració plena del culte cristià. De l’any 900 la basílica de Sant Just i Sant Pastor conserva la lauda sepulcral de Witiza, la més antiga de la Tarraconense, en la qual apareixen les datacions de l’era hispànica, de l’encarnació i la dels reis francs. L’antiga església visigòtica probablement hauria estat substituïda per una edificació romànica. D’aquesta època estan documentades, a més, dues capelles, una d’elles dedicada a sant Celdoni, màrtir de Calahorra.