Kościół na Górze Ślęży swoją historią sięga początków XII w. za panowania Bolesława III.
Komes Piotr Włostowic sprowadził na Ślężę zakon augustianów, przekazując im na własność Górę oraz fundując na szczycie świątynię i klasztor. Następnie zakonnicy przenieśli swoją siedzibę do Wrocławia. Piotr Włostowic podarował augustianom nadodrzańską wyspę Piasek, gdzie wraz z żoną Marią ufundowali kościół i klasztor. Stąd augustianie przez następne kilka wieków władali swoimi posiadłościami, w tym także Górą Ślężą.
Jedną z wielkich postaci związanych ze Ślężą jest piastowski książę świdnicko-jaworskiego Bolko II (ur. pomiędzy 1309 a 1312 r.), za którego panowania powstał podwójny pierścień zamków obronnych, w tym na szczycie Ślęży. Wówczas wzniesiono murowaną warownię, która przetrwała aż do XV wieku. Dziś fragmenty murów (absydy) pierwotnego kościoła oraz fundamenty średniowiecznego zamku można podziwiać przez szklaną szybę w posadce kościoła, lub zwiedzając podziemia świątyni.
Bolko II, który był wnukiem Władysława Łokietka i siostrzeńcem Kazimierza Wielkiego, przez całe życie dążył do zjednoczenia śląskiej ziemi z resztą Korony Polskiej. Dzięki niemu doszło do pokonania Krzyżaków pod Płowcami, umocnienia interesów Polski na Śląsku w ramach pokoju w Namysłowie w roku 1348. Długosz w swojej kronice napisał, że choć inni książęta śląscy zaparli się Ojczyzny – dając się zhołdować Janowi Luksemburskiemu, Niemcowi na tronie czeskim – to on jeden “nie dał się zwieść do tego grzechu, oświadczał głośno, że jest księciem polskim, a od jedności z Polską nigdy nie odstąpi”.
Za panowania Bolka II powstał także kościół pierwotny w Sulistrowicach wzmiankowany w 1352 r. Bolko II, ostatni suwerenny polski książę na Śląsku zmarł 28 VII 1368r., a dla upamiętnienia tej wielkiej postaci historycznej dzień 28. lipca jest obchodzony jako Dzień Śląska Polskiego. Za duszę księcia Bolka II od 2007 r. w ostatnią niedzielę lipca odprawiana jest Msza Św. w Kaplicy Matki Bożej Dobrej Rady i Mądrości Serca w Sulistrowiczkach u podnóża Góry Ślęży.
W drugiej połowie XVI wieku w miejscu dawnego rycerskiego zamku, Augustianie wznieśli drewnianą kaplicę, a w latach 1698 – 1702 murowaną świątynię pw. Nawiedzenia Najświętszej Maryi Panny, która przetrwała do dziś. Dnia 11 lipca 1702 roku świątynię poświęcił jej fundator i budowniczy – opat klasztoru augustianów na Piasku we Wrocławiu – Jan Sievert.
Po pożarze w 1834 roku świątynia uległa zniszczeniu. Odbudowano ją w latach 1851-1852 po odezwie do Ślązaków przez ks. kardynała Melchiora von Diepenbrocka.
Po II wojnie światowej kościół ulegał powolnej dewastacji. Staraniem ks. bp. Rektora Pawła Latuska w 1967 roku przeprowadzono remont świątyni. Prace wykonali klerycy Seminarium Duchownego i pracownicy Kurii. Wówczas wznowiono odprawianie nabożeństw.
W roku milenijnym 2000 – na polecenie ówczesnego kardynała metropolity wrocławskiego – kościół wyremontowano. W latach 2004-2006 archeolodzy z Uniwersytetu Wrocławskiego prowadzili pod świątynią prace związane z poszukiwaniem przejawów starożytnej słowiańskiej cywilizacji. Od tej pory kościół na Ślęży był zamknięty dla wiernych i turystów, oraz ulegał powolnej dewastacji.
W 2012 roku świątynia została przekazana pod opiekę duszpasterską księdzu dr. prał. Ryszardowi Staszakowi, proboszczowi parafii w Sulistrowicach, który podjął się trudnego zadania ratowania zniszczonej świątyni. Od tego momentu dzięki wspólnym staraniom obecnego arcybiskupa metropolity wrocławskiego Józefa Kupnego, księdza proboszcza, władz samorządowych w Sobótce, Miłośników Ziemi Ślężańskiej oraz życzliwych ludzi i parafian – rozpoczęto starania przywrócenia sakralnego, historycznego jak i turystycznego waloru tego miejsca. Prace związane z odbudową kościoła trwają do dziś.