„Ciebie wychwala Maryjo najświetniejszy austriacki dom arcyksiążęcy i cesarski w Wiedniu. Wychwala niezliczonymi nazwami w świątyniach, w których Ty udzielasz cudownie swych łask. Także w Starym Wielisławiu w Czechach, gdzie jesteś błogosławieństwem chorych”
Fragm. kazania, wygłoszonego w kościele w Starym Wielisławiu 8 września 1676 r.
przez Abrahama a Santa Clara, kaznodzieję dworu cesarskiego w Wiedniu
Kościół w Starym Wielisławiu należy do najstarszych w Ziemi Kłodzkiej, istniał już podobno w X w., chociaż źródła wymieniają go po raz pierwszy dopiero w 1300 r. Już wtedy świątynia musiała odgrywać znaczącą rolę w regionie, gdyż papież Bonifacy VIII w swojej bulli ustanowił ją kościołem pielgrzymkowym (z czym związane były liczne odpusty) i nazwał „Przybytkiem Niebieskim”. Być może już wówczas w kościele znalazła swoje miejsce cudowna figura Matki Boskiej, którą wg legendy miał wyrzeźbić miejscowy chłop nazwiskiem Schneider.
W 1428 r. kościół został splądrowany i spalony przez husytów (od zniszczenia miała ocaleć jedynie figura Maryi).
Świątynię szybko odbudowano. Już w 1435 r. proboszcz wielisławski przewodniczył uroczystemu ingresowi nowego proboszcza w Bystrzycy. Kolejnym dowodem jest informacja o nowych dzwonach w kościele z 1438 (z umieszczonym na nim imieniem patronki – św. Katarzyny) oraz z 1439 r. Śladem po tej XV-wiecznej budowli jest gotyckie, pięcioboczne (z dużym łukowym oknem w każdej ścianie) prezbiterium z krzyżowo żebrowym sklepieniem i czterema przyporami, a także zachowane loże kolatorskie (nad zakrystią i po przeciwnej stronie), do których prowadzą osobne wejścia (z tyłu kościoła) i w których zasiadali właściciele wsi i patroni kościoła. W następnych latach wybudowano wieżę kościelną (1524 r.), na której zawieszono największy z dzwonów (z 1490 r.), który wzywał wiernych na modlitwę i ostrzegał przed niebezpieczeństwami.
Kolejne grabieże świątyni (np. w 1575 r. za proboszcza Fechtnera) i prześladowania ze strony protestantów, spowodowały prawdopodobnie budowę muru wokół kościoła. Z obwarowania wyróżnia się szczególnie okazały budynek bramny, na którym widnieje data budowy (1569 r.). W ich obrębie, wokół Domu Bożego, znajdował się cmentarz parafialny.
Kościół w Starym Wielisławiu skutecznie opierał się postępującej na Ziemi Kłodzkiej fali protestantyzmu. O ile w 1577 r. był jedną z pięciu parafii katolickich, o tyle w 1618 r., gdy wybuchała wojna 30-letnia była to już jedyna parafia katolicka w Hrabstwie Kłodzkim. To właśnie miejscowemu proboszczowi – Hieronimowi Heckowi, po odzyskaniu tych ziem, cesarz austriacki powierzył misję odbudowy katolicyzmu w regionie.
Kolejni proboszczowie czynili liczne zabiegi aby przywrócić kościołowi jego pielgrzymkowy charakter. Johann Friedrich Ruppert (1644 –1666) rozpowszechnia pierwsze pisemne relacje o cudownych aktach łaski Wielisławskiej Madonny.
Wydana w połowie stulecia w Augsburgu teka miedziorytów, zawiera przedstawienie Matki Boskiej Wielisławskiej opatrzone podpisem: „Pełna łaski Maria, odwiedzana przez lud, ponieważ czyni cuda”. W tym też czasie XIV-wieczna figura miała zostać przeniesiona ze skromnego miejsca w bocznym ołtarzu do ołtarza głównego, gdzie staje się celem adoracji coraz liczniejszej rzeszy pielgrzymów. Na początku XVIII w. Georg Franz Brase (1680 – 1713) opisał cudowne początki kościoła w Wielisławiu „za sprawą boską”, a kolejny proboszcz – Dawid Siesmann (1713 – 1729) napisał „Marianischer Ehrenschall”, w której zebrał informacje o cudach dokonanych za wstawiennictwem Wielisławskiej Madonny.
Zabiegi obydwu duszpasterzy o uzyskanie papieskiego odpustu dla kościoła zostały uwiecznione sukcesem w 1723 r. Papież Innocenty XIII najpierw wydaje orzeczenie o rzeźbie jako „obrazie łaski”, a następnie dekret konsystorialny nadający kościołowi tytuł „pełen łaski”, zalecający szczególna adorację Marii Wielisławskiej. Odtąd miejsce odwiedzały procesje pielgrzymów.
Odnotowano, że w l. 1729 – 1763 do kościoła wpłynęło aż 330 cennych darów wotywnych (!). Niewielka, jednonawowa (obecna nawa główna) świątynia, stała się zbyt „ciasna” dla wiernych.
W 1776 r. zakończył się pierwszy etap przebudowy kościoła. Trzynawowa świątynia z emporami nad nawami bocznymi mogła pomieścić teraz rzesze wiernych, stanowiąc jednocześnie uroczystą oprawę dla sprawowanego kultu. W 1775 r. przystąpiono do budowy nowego ołtarza głównego. Zachowany w archiwum praskim dokument z 11 kwietnia tego roku zawiera prośbę dziekana, skierowaną do wikariusza kłodzkiego, aby zezwolił na sprzedaż darów wotywnych, ponieważ wystrój ołtarza ma kosztować 500 talarów, a z datków uzyskano tylko 400. Trzykondygnacyjny ołtarz wykonany jest z drewna. Spis inwentarzowy kościoła z 1776 r. wspomina także o kracie z dwoma żelaznymi furtami i 4 ciężkimi obręczami w prezbiterium, która „na noc strzegła cudownej figury”.
Świątynię przebudowano ponownie pod koniec lat 90-tych XVIII w. Epitafium nagrobne proboszcza Karla Rögera (1792 – 1807) zawiera informację, że za jego posługi „poszerzono kościół”. Prace polegały m.in. na włączeniu wieży (przylegającej dotąd do ściany zachodniej) w obręb budowli. Wybito w niej wejście do wnętrza i opatrzono je kamiennym portalem z wizerunkiem patronki kościoła św. Katarzyny. Zmieniono także elewację północną przez wprowadzenie symetrii w rozmieszczeniu okien i podkreśleniu głównej osi okazałymi schodami i portalem (wyryto w nim datę 1796). Rozpoczęto również budowę krytych krużganków z 7 kaplicami obrazującymi boleści Matki Bożej i stacjami drogi krzyżowej (restaurowane w 1816 r.). W tym czasie w nawie północnej umieszczony został czwarty ołtarz, najmniejszy, w stylu klasycystycznym (1801). Kościół przetrwał po dziś dzień w niezmienionym kształcie.
Po II wojnie światowej opiekę nad wielisławską parafią sprawował proboszcz z Polanicy. Od 1972 r. objęli ją sercanie biali czyli zakonnicy ze Zgromadzenia Najświętszych Serc Jezusa i Maryi oraz Wieczystej Adoracji Najświętszego Sakramentu Ołtarza.
W 2000 r. Ks. Kardynał Henryk Gulbinowicz Metropolita Archidiecezji Wrocławskiej reaktywował Sanktuarium Matki Bożej Bolesnej w Starym Wielisławiu. Rok później Sanktuarium Wielisławskie podniesione zostało do rangi Sanktuarium Międzynarodowego. Uroczystościom przewodniczył Ks. Kard. Luigi Pogii z Watykanu, osobisty wysłannik papieża Jana Pawła II.
Dziś w kościele przechowywane są relikwie Krzyża Świętego, św. Katarzyny Aleksandryjskiej, replika gwoździa jakim przybito rękę Pana Jezusa do krzyża oraz relikwie św. Jana Pawła II.