O zgodnji prisotnosti krščanstva v mestu priča legenda o škofu Maksimilijanu, celjskemu rojaku, ki naj bi tu leta 284 umrl mučeniške smrti. Nova religija se je v Celju in okolici pričela hitro širiti, posebno po letu 380, ko so v protiutež vse pogostejšim germanskim vdorom (Goti so leta 380 povsem porušili Poetovio) v Celeii postavili škofijsko stolico. Že leto dni kasneje se na cerkvenem zboru v Ogleju omenja verjetno prvi celeianski škof Tenax. Kasneje se omenjata še Gavdencij in kot zadnji celeianski škof Ivan I. (579, 597 in 599).
V dokaz razširjenosti krščanstva velja omeniti najdbo ostankov starokrščanske bazilike, edine najdbe te vrste pri nas, ki so jih odkrili pri gradnji celjske pošte leta 1897. Pri odkopavanju zemlje za temelje so odkrili tlak starokrščanske cerkve iz IV. stoletja, bazilike, s tremi ladjami. Tlak, mozaik, so sestavljali majhni raznobarvni kamenčki. Popolnoma so odkrili apsido, polkrožen in vzvišen prostor za oltar in duhovščino. Absida je merila 13 m v širino in 8 m v dolžino. Ob steni je bil 2,7 m širok pas mozaika. Kamenčki so sestavljali okraske raznih oblik, največ trikotnike, kvadrate in kroge. Zanimivi so bili tudi napisi vernikov, različnih darovalcev, predvsem na srednji ladji. Njen severni del pa se je ohranil v dolžini 22 m, kar priča o izjemnosti celeianske starokrščanske bazilike.
