U memoarima sudije Stojana Simić zapisan je podatak da je prva crkva u Zaječaru podignuta 1830. godine. Bila je to, zapravo, samo mala kapela od drveta koja je služila za najnužnije crkvene potrebe.  „Ovu činjenicu treba shvatiti u kontekstu tadašnjih društveno – političkih prilika. Srbija je tek 1830. dobila izvesne privilegije koje su se ogledale u stvaranju autonomnih organa, većih ovlašćenja ali i slobodi veroispovesti… U tek osnovanoj Kneževini bilo je potrebno stvoriti državni aparat, a samim tim i institucije, od samog početka, a u odnosu na veoma skromne ekonomske mogućnosti. Iz tog razloga su i prva zdanja građena od slabog materijala i zato, često, već posle prve ili druge decenije rušena, ustupajući mesto novim, solidnijim, kao što je bio slučaj i sa zaječarskom crkvom.”¹

Po nalogu kneza Miloša, 1833. godine započele su pripreme za izgradnju nove, velike gradske crkve. Lično interesovanje samog Kneza znatno je ubrzalo radove, tako da je saborni hram Roždestva Presvete Bogorodice sazidan za samo šest meseci. Kada se sa gradnjom stiglo do krova, Knez šalje pismo u kojem daje precizno uputstvo gde na crkvi treba uklesati natpis sledeće sadržine:

„Godine 1834. sazida se cerkva ova Roždestva Presvete Bogorodice blagodetelstvom Blagotvornoga kneza Miloša Teodorovića Obrenovića pri pravoslavnomu Mitropolitu Serbskomu Petru, na slavu Božiju i za spomen posećenija, kojima je Knez Miloš mesto ovo i ove predele posetio meseca Avgusta 1834, i Jula 1833. godine kada su ovi, 20 godina bivši otrgnuti predeli Kruševac, Paraćin, Ražanj, Aleksinac, Svrljig-Banja, Banja, Gurgusovac, Crna Reka, Krajina, Ključ, Jadar i Rađevina, milošću Božjom Serbii nanovo prisoedinili.“

Po završetku gradnje počelo je unutrašnje uređenje hrama: zabeleženo je da su majstori iz Knjaževca izradili Časnu trpezu i Vladičanski tron, a prvi ikonostas delo je Georgija Bakalovića iz Karlovaca. Ovaj ikonostas je, osim nekoliko ikona iz gornje zone, stradao je u srpsko turskom ratu, a novi je oko 1880. godine uradio Nikola Marković. Krajem decenije dozidana je priprata, napravljen hor i ozidan zvonik. Početkom devedesetih godina 20. veka novi živopis oslikali su ukrajinski majstori, a prvoj deceniji novog milenijuma crkva je dobila nova zvona, trem i urađen plato.²  Mala Gospojina, odnosno dan rođenja Presvete Bogorodice 21. septembar, slavi se kao gradska slava.