W 1906 roku utworzono na terenie Orzesza kurację, która powstała z części parafii w niedalekim Wielkim Dębieńsku i części pobliskich Woszczyc (dziś chyba najbardziej zielona dzielnica Orzesza). W 1912 roku podniesiono ją do rangi samodzielnej parafii, a kuratusem i pierwszym proboszczem parafii został ksiądz Józef Kulig. Do nowo utworzonej parafii należał wówczas mały kościółek do dziś zlokalizowany na Wzgórzu Św. Wawrzyńca, pochodzący z ok. 1599 roku; jego pojemność nie była jednak wystarczająca dla powiększającej się parafii, stąd postanowiono w latach 1926-30 wybudować w centrum miasta nowy kościół pw. Nawiedzenia Najświętszej Maryi Panny. Poświęcenia świątyni dokonano w dniu 14.12.1930 roku, a towarzyszącej temu uroczystości przewodniczył ksiądz Aleksander Skowroński z Mikołowa (ówczesny proboszcz parafii św. Wojciecha i działacz społeczny). Konsekrację świątyni przeprowadzono dopiero w roku 1960.
Wystrój wnętrza tej świątyni jest dziełem Edmunda Czarneckiego i Karola Gierlotki. Kościół wybudowany został w neostylu, który przypomina styl neoromański, a dowodem na to jest zastosowanie przez projektanta triforiów w oknach. Sylweta świątyni cechuje się surowym wyglądem, może ze względu na budulec, którym jest kamień. Jej elewacje są nieotynkowane, czyli nawiązujące swym charakterem do epoki (ostrożnie oceniając) wczesnego romanizmu i rozwiniętego romanizmu. Ogólnie wygląd budowli może się odnosić do świątyń w Rudzie Śląskiej-Kochłowicach, miejscami przypomina też kościół pw. św. Wawrzyńca i Antoniego w Rudzie Śląskiej-Wirku.
Budowla ma nieco "przyciemnione" elewacje ze względu na obecność w Orzeszu - w szczególności w okolicach drugiej połowy XIX wieku - zakładów przemysłowych, potem zaś z powodu wybudowania ok. lat 30. XX wieku huty "Łaziska" i wpływu jej działalności na okolice; jednocześnie nadaje to orzeskiej świątyni charakteru surowości, a może nawet - w pewnym sensie - przyczynia się do zadumy parafian udających się na Mszę. Jednak gdyby wyczyszczono elewacje świątyni, wówczas zapewne odzyskałaby swój pierwotny blask, lecz ten "przyciemniony" kolor w zasadzie dodaje jej ciekawego wyglądu. Taki zabieg przeprowadzono w przypadku katowickiego, potocznie zwanego "kościoła mariackiego" i efekt właściwie jest nijaki, zaś przed oczyszczeniem znacznie przypominał katedrę w Kolonii.