Według starej tradycji przekazanej przez Ignacego Wawrzyńca H. Kapicę Milewskiego (1763-1817), rejenta grodzkiego brańskiego, pierwsza świątynia w Bielsku, zwanym też Bielsko została wzniesiona przez króla Władysława II Jagiełłę (ok. 1362-1434) - po chrzcie Litwy w 1386 roku. Kościół parafialny pw. Narodzenia NMP, św. Mikołaja i Trzech Króli został ufundowany z pewnością przed 1430 r. przez Witolda (ok. 1348-1430), wielkiego księcia litewskiego (1413-1430). W tym roku (9 stycznia) wielki książę nadał szlachetnemu Andrzejowi wójtostwo w Bielsku (na prawach dziedzicznych), z poleceniem osadzania w mieście katolików: Polaków i Niemców.
W 1446 roku Kazimierz IV Jagiellończyk (1427-1492) nadał ks. Hieronimowi, proboszczowi bielskiemu dwóch włościan i daninę miodową. W 1457 roku proboszczem w Bielsku był ks. Chwalisław; w latach 1470-1473 roku ks. Klemens, a w 1474 ks. Maciej (Matjasz), wzmiankowany w latach 1474-1498, który zbudował w 1492 roku okazały drewniany kościół w stylu bazylikowym, a także: szkołę, dom dla nauczania rzymskokatolickich księży, budynki zajmowane przez proboszcza, ogród i cmentarz. Na prośbę ks. Macieja wielki książę litewski Aleksander Jagiellończyk (1461-1506) w poniedziałek w wigilię Narodzenia Pańskiego 1492 roku potwierdził witoldowe uposażenie, które stanowiły między innymi wsie: Pulsze i Kołby z ich chłopstwem (później doszły jeszcze: Samułki, Misiuki, Malinowo), łąki za Kotowiczami, dziesięcinę z niektórych majątków skarbowych i prywatnych; pozwolił zbudować młyn na rzece Żabiej w Pulszach, itd. Po 1506 roku król Zygmunt I Stary (1467-1548) wzniósł przytułek dla biednych z kaplicą św. Marcina (przy potoku Sered, po prawej stronie ul. Litewskiej), który był utrzymywany z dochodów z młyna wodnego Kiszczyn na rzece Białej oraz z ziemi nazywanej Wochnowszczyzna. W 1521 roku legat i nuncjusz papieski Zachariasz Ferreri nadał odpusty temu szpitalowi. Dawne nadania dla kościoła potwierdzali później: we wtorek po św. Łucji 1512 roku - król Zygmunt I Stary oraz w 1535 r. jego żona królowa Bona Sforza d’Aragona (1494-1557). Dzięki jej fundacji w 1535 roku kościół został odrestaurowany i podniesiony do godności prepozytury przez ks. Pawła Algimunta, księcia Holszańskiego (1485-1555), biskupa łuckiego (1507-1536). Oryginalne dokumenty kościoła parafialnego bielskiego z lat 1512-1575 przechowywane są obecnie w Archiwum Archidiecezjalnym w Białymstoku. Od 1604 roku Bielsk Podlaski stał się siedzibą dekanatu.
W latach „potopu szwedzkiego” (1655-1660) kościół został ograbiony i zdewastowany przez wojska kozackie i Jerzego Rakoczego II (1621-1660), księcia siedmiogrodzkiego (1648-1658) oraz w czasie najazdu wojsk moskiewskich kniazia Iwana Chowańskiego (1659-1660). W latach 1670-1674 roku na miejscu dotychczasowej świątyni wzniesiono nową, kosztem kanonika krakowskiego (od 1660) ks. Jana Małachowskiego herbu Nałęcz (1623-1699), prepozyta bielskiego (1666-1676), późniejszego biskupa chełmskiego (1676-1681) i krakowskiego (1681-1699). W 1679 roku świątynię przebudowano przy pomocy majstrów sprowadzonych z okolic Lublina. Na prośbę ks. kan. Mikołaja Tomisławskiego, prepozyta bielskiego (1688-1715), nową świątynię konsekrował w dniu 28 marca 1688 roku ks. Mikołaj Popławski herbu Trzaska (1636-1711), biskup inflancki (1685-1711). W 1770 roku hetman Jan Klemens Branicki (1689-1771) z Białegostoku, starosta brański (1709-1752), zbudował pod kościołem fundamenty i trzy piwnice. W marcu 1783 roku tenże kościół został rozebrany.
Na jego miejscu w latach 1783-1784 roku zbudowano istniejący do dzisiaj murowany kościół, z pomocą władz miejskich i kosztem siostry ostatniego króla Polski - Izabeli Branickiej z Poniatowskich, zwanej „Panią Krakowską” (1730-1808), żony wspomnianego Jana Klemensa Branickiego. Projektantem tej noeklasycystycznej świątyni był warszawski architekt Szymon Bogumił Zug (1733-1807), a kierownikiem budowy Jan Andrzej Zschernig (Czernisz). Fundamenty do nowej świątyni zaczęto zakładać 23 kwietnia 1783 roku. Drewno ofiarował z lasów królewskich Stanisław II August Poniatowski, król polski (1764-1795). Pierwsze nabożeństwo zostało w nim odprawione już 1 listopada 1783 r. Konsekracji dokonał dnia 9 października 1796 r. ówczesny proboszcz bielskiej prepozytury (1756-1797) ks. Jan Szyjkowski (1721-1797), biskup tytularny Sinope (13.11.1775), sufragan diecezji łucko-brzeskiej (1775-1797).
W 1816 roku staraniem ks. Mikołaja Andruszkiewicza, administratora bielskiego (1815-1816), zostały wstawione - w miejsce starych - nowe, trzygłosowe organy, które wykonał w 1815 roku warszawski organmistrz Dominik Pilichowski. Ich fundatorem był proboszcz białostocki ks. Kazimierz Kubeszowski (1765-1833). W 1816 roku cmentarz kościelny ogrodzono kamiennym murem, a w 1843 roku - staraniem ks. Jana Izbickiego proboszcza bielskiego (od 1823) - zbudowano obok kościoła murowaną dzwonnicę, zawieszając w niej dzwon zakupiony przez Aleksandra Bogusza, regenta ziemi bielskiej (1786). W 1902 roku staraniem ks. Adolfa Bilmina (1865-1904), proboszcza bielskiego (1899-1904), na ich miejsce wstawiono nowe (służą do dzisiaj), które wykonał organmistrz Piotr Wojciechowicz z Wilna. W 1912 roku - za czasów ks. Jana Nieczyporowicza (1877-1919), proboszcza bielskiego (1911-1919), sklepienie świątyni ozdobiono polichromią przedstawiającą Dwunastu Apostołów oraz położono posadzkę z terakoty.
W czasie działań wojennych w 1944 r. kościół został częściowo uszkodzony (rozbita ściana boczna, szyby, dach, zniszczony ołtarz i obraz św. Mikołaja). Konieczne remonty przeprowadzili: ks. Michał Sokołowski (1910-1980), ówczesny proboszcz (1943-1946) i ks. prał. Bronisław Kiełbassa (1883-1961), proboszcz i dziekan bielski (1946-1961). W 1988 roku kolejne poważne remonty podjął ks. mgr Antoni Zajączkowski (1944-1990), proboszcz parafii farnej (1987-1990), które - po jego nagłej śmierci - kontynuował ks. prał. dr Ludwik Olszewski.
W 1996 roku parafia obchodziła jubileusz 200-lecia konsekracji kościoła. Z tej okazji Ojciec Święty Jan Paweł II - na prośbę ks. Antoniego P. Dydycza, biskupa drohiczyńskiego - wyniósł 28 sierpnia tegoż roku bielską świątynię do godności Bazyliki Mniejszej.
Szczególnym wydarzeniem w życiu parafii było wyniesienie na ołtarze ks. kan. Antoniego Beszty - Borowskiego (1880-1943), proboszcza i dziekana bielskiego (1927-1943), który z grupą 50. bielszczan został bestialsko zamordowany przez Niemców w Lesie Pilickim, dnia 15 lipca 1943 roku. Ojciec Święty Jan Paweł II, w czasie pielgrzymki do Ojczyzny 13 czerwca 1999 r. w Warszawie, zaliczył go do grona błogosławionych wśród 108. polskich męczenników II wojny światowej. W rok po beatyfikacji, dnia 15 lipca 2000 r. doczesne szczątki bł. ks. Antoniego zostały uroczyście przeniesione z parafialnego cmentarza i złożone w relikwiarzu - trumience, która znajduje się w podstawie ołtarza bocznego Matki Bożej Różańcowej w Bazylice Mniejszej w Bielsku Podlaskim. Z dniem 2 lutego 2010 roku przy Bazylice Mniejszej w Bielsku Podlaskim ks. bp Antoni P. Dydycz powołał Podlaską Kapitułę Kolegiacką, ustanawiając bielską świątynię kolegiatą. Pierwszym prepozytem Kapituły został ks. prał. dr Ludwik Olszewski, proboszcz parafii w latach 1990-2012.
Na placu przykościelnym stoi murowana, dwukondygnacyjna dzwonnica zbudowana w 1843 roku w stylu klasycystycznym, staraniem ks. Jana Izbickiego (ur. 7 lutego 1793), proboszcza bielskiego (1828-1850). Po drugiej stronie ulicy stoi nowa, murowana, zbudowana w latach 1981-1986, staraniem ks. mgr. Tadeusza Tararuja (1919-1987), proboszcza bielskiego (1970-1987) oraz ks. Jana Koca, ówczesnego wikariusza (1975-1987), a następnie administratora tejże parafii (1987). W jej pobliżu znajduje się zabytkowa drewniana plebania, zbudowana w latach 1900-1903 staraniem wspomnianego ks. Adolfa Bilmina, która w latach 2000-2003 została odrestaurowana przez ks. prał. dr. Ludwika Olszewskiego i przeznaczona na Dom Pamięci bł. Ks. Antoniego Beszty - Borowskiego. W głębi posesji tuż przy ulicy stoi jeszcze jeden dom parafialny z 1909 roku, w którym, po gruntownym remoncie w latach 1999-2000 - przeprowadzonym przez ks. Ludwika Olszewskiego, mieści się obecnie Parafialny Oddział Caritas, Księgarnia bł. Antoniego Beszty-Borowskiego i świetlica „Promyk Dnia”.
Oprac. ks. dr Zbigniew Rostkowski
