Kościół św. Mikołaja w Brzegu powstawał w latach 1370-1420 za czasów rządów księcia Ludwika I. Wybudowano go w miejscu starszej, murowanej budowli, którą wymienia się w źródłach w 1279 r. Budowla została sfinansowana przez mieszczan i księcia. Rajcy miasta zamówili projekt u mistrza wrocławskiego Gunthera, który powtórzył schemat wrocławskich kościołów: św. Marii Magdaleny oraz św. Elżbiety.
Kościół ma trzynawową charakterystykę bazyliki z wydłużonym korpusem pozbawionym podziału na chór i partie naw. Strzelistość nawy głównej z gwiaździstym sklepieniem i wysmukłymi oknami skontrastowano z niskimi, szerokimi i ciemnymi nawami bocznymi. Nawę główną od bocznych oddzielono prostymi filarami i linearnymi przęsłami, nie ograniczającymi przestrzeni wnętrza. Kościół posiadał bogaty wystrój rzeźbiony w drzewie oraz zespół witrażowy. Do dzisiaj zachowały się tylko fragmenty. Drewniane części spłonęły podczas II wojny światowej, a szczątki wyposażenia znajdują się w Muzeum Narodowym we Wrocławiu oraz w Muzeum Piastów Śląskich w Brzegu. Natomiast dwie kwatery oryginalnych witraży znajdują się w Muzeum Narodowym w Poznaniu.
W 1523 r. w Brzegu zwyciężyła reformacja. Książę Fryderyk II wprowadził w księstwie wyznanie luterańskie, jako obowiązujące. Już w 1525 roku kościół św. Mikołaja zaczął funkcjonować jako kościół protestancki. Taką rolę pełni aż do 1945 roku. W ściany i filary kościoła wmurowywano kamienne i drewniane epitafia bogatych mieszczan brzeskich. Pod koniec XIX wieku nadbudowano wieże kościoła jako odpowiedź na podwyższenie wież w katolickim kościele Podwyższenia Krzyża Świętego.
Podczas zdobywania miasta na przełomie stycznia i lutego 1945 r. kościół doszczętnie spłonął, a następnie przez 13 lat (do 1958 r.) niszczał pozostawiony bez opieki. W 1958 r. z inicjatywy księdza Kazimierza Makarskiego podjęto się odbudowy kościoła według wzorów z 1370 r. Odkryto wówczas w zakrystii późnogotyckie freski ścienne.
Obecnie kościół funkcjonuje jako świątynia katolicka. Zaliczany jest do jednych z największych bazylik gotyckich na Śląsku.