Kościół w stylu neoromańskim wybudowany został z inicjatywy ewangelickiego pastora Karola Appenroth. Wcześniej za zgodą Diecezji Opolskiej ewangelicy odprawiali swoje nabożeństwa w katolickim kościele p.w. św. Walentego.

W roku 1846 wielki pożar jaki ogarnął miasto w znacznej części uszkodził również katolicki kościół. Za zezwoleniem księcia Wilhelma z Brunszwigu (ówczesnego właściciela Dobrodzienia) nabożeństwa ewangelickie odprawiano w salach zamkowych. Kościół wybudowany został z darowizny księcia i składek parafian. Świątynię poświęcono p.w. św. Marii Magdaleny.

Po II wojnie światowej kościół przejęty został przez katolików, jego konsekracji dokonał abp Bolesław Kominek pod wezwaniem Nawiedzenia NMP. Podczas wymiany pokrycia dachu kościoła i wieży w złoconej kuli odnaleziono wiele XIX wiecznych monet oraz spisaną krótką historię świątyni. Wysokość wieży kościelnej łącznie z krzyżem wynosi 27 metrów.