Parafia należy do dekanatu mysłowickiego w archidiecezji katowickiej, została erygowana 1 paździenika1903 r.

Kościół został wybudowany na ziemiach podarowanych przez Andrzeja Sorka, według planów, których autorem był architekt Ludwig Schneider z Katowic. Budowę rozpoczęto jesienią 1892 r., a prace 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 wyboru takiego wezwania mogły się przyczynić nagłośnione objawienia Matki Boskiej z Lourdes w 1858 r. 22 listopada 1893 r. mysłowicki proboszcz ks. Franciszek Klaszka pobłogosławił (dawniej: poświęcił) kościół. Część wystroju wewnętrznego kościoła oraz organy były darem z rozebranego kościoła bożogrobców w Chorzowie Starym. Po pobłogosławieniu kościoła mieszkańcy Brzezinki uciekli się do podstępu, aby prosić biskupa wrocławskiego o utworzenie 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 brzezińskiego kościoła, jednak obiecał przysłać księdza. 15 października 1902 r. ks. Emil Wawreczko – mysłowicki wikary – został posłany przez kard. Georga Koppa do pracy duszpasterskiej w Brzezince. Ks. Wawreczko zatroszczył się o powstanie cmentarza, odnowienie ołtarza i budowę dwóch ołtarzy bocznych. 31 marca 1903 r. kardynał Georg Kopp z Wrocławia podpisał dokument erygujący parafię w Brzezince, który wszedł z życie 1 października 1903 r.

27 października 2013 r. abp. senior Damian Zimoń poświęcił (dawniej: konsekrował) świątynię.

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.