Świątynia należy do najstarszych zabytków miasta, choć pierwszeństwo w tym względzie przypada pochodzącej najprawdopodobniej z XII wieku świątyni św. Stanisława Biskupa i Męczennika w Starym Bielsku, gdzie istniała najstarsza bielska parafia.
W rozwijającym się dynamicznie w średniowieczu grodzie, położonym na szlaku handlowym łączącym Kraków i Morawy, z czasem stanął zamek książęcy, a w jego sąsiedztwie cały kompleks zabudowań miejskich. Tu także, zgodnie z postanowienie fundatora: księcia Wacława I z dynastii Piastów, od 1443 roku powstawał gotycki kościół św. Mikołaja. Był budowany z kamienia i cegły, a konsekrowany został w 1447 roku. Prawdopodobnie zastąpił stojącą w tym miejscu wcześniej drewnianą świątynię.
W tym samym 1447 roku erygowana została parafia św. Mikołaja, która zarazem otrzymała status głównej parafii miasta. Przy kościele św. Mikołaja obok zabudowań plebanii powstał szpital i szkoła. W pierwszym okresie przy świątyni znajdował się cmentarz. Patron parafii, otaczający szczególną opieką kupców, był też patronem miasta.
Od 1654 r. na mocy dekretu biskupa wrocławskiego Karola Ferdynanda proboszczom bielskim przysługiwał tytuł archiprezbitera, dziekana, a pozostałe świątynie, wznoszone w Bielsku i okolicznych wsiach, m.in. w Wapienicy czy Kamienicy, miały status kościołów filialnych, podobnie jak najstarszy kościół: św. Stanisława w Starym Bielsku.
W tamtym okresie Bielsko było najdalej wysuniętą w kierunku wschodnim parafią diecezji wrocławskiej. Wskutek zmian politycznych po 1770 r. znalazło się w obrębie wydzielonego przez biskupa wrocławskiego generalnego wikariatu dla austriackiej części tej diecezji, obejmującej głównie teren Śląska Cieszyńskiego. Po 1925 r. wraz z pozostałymi parafiami polskiej części Śląska Cieszyńskiego weszło w skład diecezji katowickiej, a od 1992 r. Bielsko-Biała znalazło się w obrębie utworzonej przez papieża Jana Pawła II bullą „Totus Tuus Poloniae populus” diecezji bielsko-żywieckiej. Mocą tej samej bulli Bielsko-Biała stało się stolica diecezji, a kościół św. Mikołaja został podniesiony do rangi katedry.
Wstawała z popiołów
W wyniku reformacji od 1559 r. kościół św. Mikołaja, podobnie jak większość świątyń katolickich na terenie Śląska Cieszyńskiego, znajdował się w rękach ewangelików. Na początku siedemnastego stulecia na wysokości prezbiterium, od strony północnej, dobudowana została kaplica rodowa Sunneghów, którzy jako właściciele Bielska sprawowali też obowiązki kolatorów świątyni. Wspólnocie katolickiej zwrócony został w 1630 r. Od tego roku wznowiona została także działalność szkoły.
Na przestrzeni wieków świątynia kilkakrotnie padała ofiarą pożarów, które niszczyły ją podobnie jak okoliczną zabudowę miasta. Po pierwszym z pożarów, który dotknął miasto w 1659 r., dzieło odbudowy kościoła wspierał ówczesny właściciel Bielska baron Juliusz Sunnegh. Wtedy powstała pierwsza kościelna wieża, dobudowana do nawy kościoła.
Kolejny fundator, Juliusz Gotlieb Sunnegh zakupił dla świątyni nowe wyposażenie wnętrza, w tym ołtarze boczne i ołtarz główny z obrazem św. Mikołaja, poświęcone w 1719 r. Radość parafian z nowego wystroju świątyni nie trwała długo.
Wnętrze kościoła uległo całkowitemu zniszczeniu podczas następnego pożaru, wywołanego w 1750 r. przez uderzenie pioruna. Wtedy zniszczone zostały również dzwony i zegar kościelny. Fundusze na odnowienie zniszczone świątyni przekazał ówczesny właściciel Bielska Aleksander Józef książę Sułkowski, a to dzieło wsparli także zamożniejsi mieszczanie: kupcy i rzemieślnicy. Ród książąt Sułkowskich sprawował opiekę nad świątynią od 1752 roku aż do 1945 roku.
Odbudowany kościół poświęcony został ponownie w 1756 roku. W kolejnych dziesięcioleciach miasto dotknęły trzy trzęsienia ziemi, jednakże nie naruszyły one konstrukcji kościoła w poważniejszy sposób. Ogromne straty spowodował natomiast pożar, do którego doszło w 1808 roku. Spłonęła wówczas cała świątynia z wyposażeniem i plebanią. Gruntowna odbudowa trwała kilkanaście lat, a nowy wystrój wnętrza, obejmujący m.in. ołtarz główny i pięć ołtarzy bocznych, był dziełem wiedeńskich artystów i powstał w stylu późnego baroku i klasycyzmu.
Kościół w nowej postaci nie przetrwał zbyt długo, ponieważ w 1836 roku doszło do kolejnego pożaru. Tym razem dzieło odbudowy połączone zostało z szeregiem dodatkowych prac budowlanych, w tym dobudowaniem wieży. Czuwał nad nimi ks. dr Mateusz Opolski, który był proboszczem i zarazem pełnił też funkcję generalnego wikariusza cieszyńskiego. Kolejny czas budowlanych zmian, związanych też z adaptacją budowli do nowych rozwiązań technicznych w zakresie oświetlenia i ogrzewania, rozpoczął się pod koniec XIX wieku, kiedy proboszczem został ks. dr Józef Bulowski, sprawujący tę funkcję do 1932 r. Na jego zlecenie powstał kompleksowy projekt przebudowy i poszerzenia świątyni, a autorem tego projektu był Leopold Bauer, znany architekt z Wiednia. W ramach tych prac przedłużona została nawa główna, dobudowano dwie nawy boczne i wysoką wieżę z czterema dzwonami. Wkrótce po wybuchu I wojny światowej dzwony skonfiskowano na potrzeby armii austriackiej, a kolejne padły ofiarą konfiskaty dokonanej przez wojska hitlerowskie. Obecne dzwony ufundowano w 1958 r.
Wielokrotne odbudowy spowodowały, że w architektonicznej bryle potężnej świątyni odcisnęły się ślady wielu epok i stylów, od zachowanych elementów pierwszej gotyckiej konstrukcji zachowanej w elementach murów prezbiterium czy średniowiecznych pozostałości części nawy, aż po dobudowane w pierwszych latach dwudziestego wieku nawy boczne, część nawy głównej i wejście główne zwieńczone trzema wieżami, a ozdobione portalem z rzeźbionymi postaciami dwunastu apostołów, a także ustawionymi na cokołach figurami patronów: św. Mikołaja, św. Jana Nepomucena i św. Jadwigi Śląskiej. Rozbudowaną świątynię w 1911 roku poświecił biskup wrocławski kard. Jerzy Kopp.
Ze św. Mikołajem i Maryją
Obecnie w ołtarzu głównym znajduje się obraz św. Mikołaja pochodzący z 1845 roku, a twórcą figury patrona umieszczonej na fasadzie, podobnie jak dwóch pozostałych rzeźb, był artysta Othmar Schimkowitz z Wiednia.
W wystroju kościoła uwagę zwracają zachowane piękne witraże. Najstarsze, wykonane jeszcze w 1894 roku, przedstawiają m.in. Serce Pana Jezusa, św. Józefa z Dzieciątkiem, św. Annę z Matką Boską. Drugą grupę stanowią secesyjne witraże z 1911 roku autorstwa Ryszarda Halfingera, przedstawiające sceny z życia Pana Jezusa, m.in. pokłon Trzech Króli, a także wydarzenia Triduum Paschalnego.
Od 1792 r. w kaplicy Sunneghów czczony jest do dzisiaj obraz MB Częstochowskiej, pochodzący z XVII wieku a przywieziony do Bielska przez krewnego właścicieli miasta, Teodora Sułkowskiego. Jego syn, Józef Sułkowski, był adiutantem Napoleona Bonapartego. Przed tym wizerunkiem Matki Bożej często modlił się ks. Józef Stojałowski, twórca licznych bielskich organizacji katolickich i działacz społeczny.
W nawie boczne od strony północnej kościoła po rozbudowie znalazł się obraz Pana Jezusa w Ogrójcu, a w prawej nawie bocznej znajdują się dziś epitafia Salomei i Zuzanny Rodler z 1622 roku.
Po wprowadzonych przez ks. Leopolda Pietroszka w latach 60. dwudziestego wieku radykalnych zmianach posoborowych z kościoła zniknęła większość elementów wystroju, a polichromie zamalowano. Od 1983 roku staraniem ks. prał. Zbigniewa Powady przywrócone zostały niektóre elementy, a w 1998 r. zrealizowano według projektu architekta Stanisława Niemczyka dostosowanie prezbiterium do wymogów swiątyni katedralnej. W tym samym czasie zrekonstruowane zostały freski, które w 1936 roku wykonali w kościele św. Mikołaja artyści: Marian Konarski i Michał Gadocha.
Ulice należące do parafii:
Bardowskiego, Barlickiego, Batorego, Bohaterów Warszawy, Browarna (3-11), Cechowa, Celna, Cieszyńska 1-109, Czajkowskiego, Czysta, Damrota, Drzymały, pl. Fabryczny, Grota-Roweckiego, Inwalidów, Kochanowskiego (1-38a), Kołłątaja, Konopnickiej 1-25, Kopernika, Kościelna, Kościuszki, Krasińskiego 1-24, Kunickiego, 11 Listopada 1-10, Lompy, Łukasiewicza, 1 Maja, 3 Maja 1-9a, Miarki, pl. Mickiewicza, Mickiewicza 1-23, pl. Św. Mikołaja, Młyńska, Modrzewskiego 2, 3, 8, 12, 15, Nad Niprem, Orkana, Pankiewicza, Partyzantów, Piwowarska, Platter, Podcienie, Powstańców Śląskich, Przechód, Przekop, Pułaskiego, Reymonta, Rynek, Schodowa, Sienkiewicza, Sikorskiego, Skargi, Słowackiego 1-19, pl. Smolki, Solna, Stojałowskiego 1-8, Sukiennicza, Wilsona, Wzgórze, Zamkowa, Zaułek, Zdrojowa, pl. Zwycięstwa 2, 3, pl. Żwirki i Wigury, Żywieckie Przedmieście