Původní kostel spadá svým založením do doby povýšení osady Bílovce na město – konec 13. století.Tento pravděpodobně dřevěný kostel byl proměněn v kamennou stavbu a roku 1422 byl opraven a goticky přestavěn. Nejstarší část kostela – obvodové zdivo kněžiště. Dva ohromné sloupy z kamene drží gotickou klenbu s výrazným žebrovím.

V první polovině 16. století byla přistavěna sakristie s depozitářem a jižní kaple. V roce 1613-1616 byla zbourána stará, většinou dřevěná věž a byla postavena věž nová. Klenba nad hlavním oltářem byla zvýšená a prodloužená směrem východním v roce 1771. V té době vznikla Bolestná kaple a severní kaple.

Půdorys kostela je ve znamení kříže. Jde o orientovanou stavbu. Na východní straně je umístěn hlavní oltář s největším obrazem v kostele (Sv. Mikuláš a sv. Jan Nepomucký se přimlouvají u Krista Pána za věřící lid). Svatému Mikuláši je kostel zasvěcen. Na bocích obrazu stojí na levé evangelní straně socha papeže Řehoře Velikého a na epištolní straně socha sv. Mikuláše. Obraz maloval významný bílovecký rodák Ivo Leicher okolo roku 1770.V kapli Bolestné je socha Piety – Panna Maria s tělem ukřižovaného Krista. Nejvzácnějším obrazem je obraz Salvator Mundi od vlámského mistra a geniálního malíře Rubense - 16. století (zde je pouze kopie)Při východu s kněžiště je na jedné straně umístěna křtitelnice a barokní kazatelna. Na zdi je řezba ukřižovaného Krista 2.pol.14.stol. Z tváře je patrné jeho bolestné utrpení. Na druhé straně je socha křtu Páně – Jan Křtitel křtí Ježíše v Jordánu, v horní části je socha Boha Otce. Na čelní zdi je socha P. Marie.Původně na hlavním oltáři s paprsky.V severní kapli je oltář sv. Anny s obrazem sv. Anny vyučující Pannu Marii a v jižní kapli je oltář sv. Rodiny.

Vzadu na kůru jsou varhany z roku 1896. Ty byly v roce 1945 za 2. světové války polozničené granátem. Jsou renovovány. Mají 18 rejstříků. Výška věže je 50, 5 metrů.

Věž má na vnějším zdivu označení dvou letopočtů: 1657 – památka 30-ti leté války – doba, kdy z Bílovce stalo opět kvetoucí město a 1945 - památka 2. světové války.Ve věži je zavěšeno pět zvonů. Svatý Mikuláš má hmotnost 1650 kg. V roce 1736 pukl a byl přelit. Ve věži je dále zvon umíráček a tři nové zvony o váze 913, 485 a 289 kg z roku 1991. Zvony byly darovány bíloveckými rodáky- kněžími, bratranci P. Ernstem a Adolfem Kretschmerem u příležitosti jejich 65 a 50 let kněžství a byly odlity v německém Pasově u firmy Perner.

V chodbě kostela jsou umístěny pamětní desky, které jsou věnovány obětem první světové války a byly na toto místo instalovány v roce 1931.