Pierwszy kościół w Bielsku ufundował podobno sam Władysław Jagiełło już pod koniec XIV w. ale pisemnie potwierdzono dopiero fundację z 1430 r. (księcia litewskiego Witolda) połączoną z nakazem osadzenia w mieście polskich i niemieckich katolików. Sześćdziesiąt lat później stała tu okazała, drewniana świątynia w stylu bazylikowym. Wiadomo, że w 1535 r. za sprawą królowej Bony poddano ją gruntownej renowacji i podniesiono do godności prepozytury.
Mocno zniszczona w czasach potopu szwedzkiego, po jego zakończeniu została praktycznie wzniesiona od nowa. W 1770 r. hetman Jan Klemens Branicki zadbał o podpiwniczenie kościoła i dobudowanie fundamentów, mimo to trzynaście lat później budowlę rozebrano i rozpoczęto wznoszenie w tym miejscu całkowicie nowej, murowanej świątyni.
Do jej powstania przyczyniła się siostra ostatniego polskiego króla - hetmanowa Branicka. Architekta (Szymon Zug) sprowadzono z Warszawy a konieczne do budowy drewno podarował sam król Stanisław Poniatowski. Pierwsze nabożeństwo w nowym, neoklasycystycznym kościele odprawiono w 1783 r. (chociaż konsekracji dokonano dopiero w 1796r.) W 1843 r. dostawiono murowaną, klasycystyczną dzwonnicę a na początku XX w. (1902) wstawiono nowe organy. Dziesięć lat później położono terakotową posadzkę i ozdobiono polichromią sklepienie.
Wyremontowany po uszkodzeniach wojennych (i po raz kolejny w 1988r.) kościół służy wiernym do dziś. Pod koniec lat osiemdziesiątych XX w. wzbogacił się o nową dzwonnicę, a w 1996 r.- z okazji dwusetlecia konsekracji - Ojciec Święty Jan Paweł II wyniósł bielską świątynię do godności Bazyliki Mniejszej.