Kościół został wybudowany na ziemiach podarowanych przez Andrzeja Sorka, według planów, których autorem był architekt Schneider z Katowic. Budowę rozpoczęto jesienią 1892 r., pracę przyspieszyło podarowanie przez biskupa dotacji w wysokości 5000 marek. 25 października tegoż roku poświęcono kamień węgielny, w który został wmurowany dokument, opisujący przebieg przygotowań do budowy kościoła, a także informacje dotyczące Brzezinki i jej mieszkańców w tamtych latach – m.in. liczba mieszkańców, kopalń, szkół, zatrudnienie, a także wymieniono najhojniejszych ofiarodawców. Z tego dokumentu dowiadujemy się, że kościół budowany był pod wezwaniem Nawiedzenia NMP; do takiego, a nie innego patronatu mogły się przyczynić nagłośnione objawienia Matki Boskiej z Lourdes w 1858 r. W 1893 r. do komitetu budowy przystąpił mysłowicki proboszcz ks. Klaszka, który pomógł wprowadzić do projektu ważne zmiany – m.in. pominięte dzwony, ogrodzenie, ołtarze, ambonę. Pojawiły się dwa poważne problemy w czasie budowy. Pierwszym z nich była słaba konstrukcja ścian, a drugim – groźba bankructwa architekta Schneidera. Pojawiła się nawet obawa, że kościół zostanie zburzony lub sprzedany, aby w ten sposób spłacić długi architekta. 22 listopada 1893 r. mysłowicki proboszcz Klaszka poświęcił kościół. Wystrój wewnętrzny kościoła był darem z rozebranego kościoła w Chorzowie, wraz z wystrojem brzezińskiemu kościołowi zostały podarowane stare organy. Po poświęceniu kościoła mieszkańcy Brzezinki uciekli się do podstępu, aby wymóc na biskupie wrocławskim stworzenie osobnej parafii. Postanowili oni zatrzymać biskupa wrocławskiego kard Georga Koppa, kiedy to 4 maja 1902 r. przejeżdżał przez Brzezinkę do Dziećkowic, aby udzielić tam sakramentu bierzmowania. Przywitany przez naczelnika Ludę kard. Georg Kopp wprawdzie nie wstąpił do Brzezinki, jednak obiecał przysłać księdza. 15 października 1902 r. ks. Emil Wawreczko – mysłowicki wikary – został mianowany przez kard. Georga Koppa pierwszym proboszczem w Brzezince, który 9 listopada został uroczyście wprowadzony na ten urząd. Ks. Wawreczko zatroszczył się o powstanie cmentarza, odnowienie ołtarza, budowę dwóch ołtarzy bocznych. 31 marca 1903 r. kardynał Georg Kopp z Wrocławia erygował parafię w Brzezince, włączając ją do dekanatu mysłowickiego. 27 października 2013 r. abp. senior Damian Zimoń konsekrował świątynię.

Brzezinka była parafią, która szybko potrafiła na swoim terenie powołać do życia stniejące w tamtych czasach stowarzyszenia kościelne. W 1903 r. w parafii zawiązała się Mariańska Kongregacja Panien, która po dwudziestu latach liczyła już 230 członkiń, co na parafię liczącą 6000 ludzi było sporym osiągnięciem. Warto zaznaczyć, że to parafia w Brzezince już w 1905 r., jako pierwsza na Górnym Śląsku, wprowadziła zwyczaj odprawiania pasterki o północy. W 1909 r. do Brzezinki przybyły Siostry Służebniczki NMP. Zajmują się katechezą i pracą z dziećmi. Opis z