Barokowy kościół – wraz z przylegającym klasztorem – został wybudowany w stylu barokowym w latach 1690 –1699 według projektu Jana Michała Linka.
Fundatorką kościoła była Maria Kazimiera, żona Jana Sobiepana Zamojskiego, późniejsza żona Jana III Sobieskiego. Kościół z jej własnego nakładu został wybudowany jako wotum za odzyskane zdrowie. Konsekracja kościoła odbyła się w 1699 r., dokonał jej biskup obrządku ormiańskiego ze Lwowa Deodat Narsesowicz.
Nad głównym wejściem do kościoła została umieszczona tablica fundacyjna w języku łacińskim, której tekst w tłumaczeniu brzmi: „ Panu Największemu kosztem i nakładem Najjaśniejszej Marii Kazimiery, Królowej Polski, towarzyszki życia świętej pamięci Jana III, Króla Polski, jako wypełnienie ślubu za odzyskane w tym miejscu, a już bezpowrotnie utracone zdrowie, ten święty przybytek został wzniesiony ku czci Najświętszej Dziewicy Maryi i poświęcony w 1699”.
Kościół jest jednonawowy, znajdują się w nim ołtarze boczne: Matki Bożej Częstochowskiej, św. Walentego, Chrystusa Ukrzyżowanego i św. Anny.
Ołtarz główny został wykonany w latach 1774 –1776 przez Jana Mauchera. Między kolumnami znajdują się postacie św. Jacka, Dominika, Wincentego Ferreriusza i Tomasza z Akwinu. W centrum ołtarza na tle kopii Matki Bożej Krasnobrodzkiej, w prawym górnym rogu został umieszczony słynący łaskami obrazek. Ma on wymiary 9×14 cm. Przedstawia Maryję w ogrodzie różanym. Ma ona ręce skrzyżowane na piersi w geście modlitwy, a oczy zwrócone na Dzieciątko Jezus leżące na pieluszkach u Jej stóp. Boże Dziecię unosi dłoń w geście błogosławieństwa. Między tymi postaciami jest symbol Ducha Świętego i modlitwy.
4 lipca 1965 r. odbyła się uroczystość koronacji obrazu Matki Bożej. Zgodnie z dekretem stolicy apostolskiej ks. bp Piotr Kałwa (ówczesny ordynariusz Diecezji Lubelskiej) poświęcił i założył korony.
Krasnobrodzki kościół wyposażony jest w 33 głosowe organy firmy kamińskich z Warszawy wykonane w 1975 r. Od 1975 r. w krasnobrodzkim kościele odbywają się – Międzynarodowe Koncerty Organowe, a od 2007 r. Ogólnopolski Festiwal Muzyki Organowej i Kameralnej „Per Artem ad Astra”.
Na dawnym cmentarzu przy kościele uwagę przyciąga wysoka figura w kształcie słupa na kwadratowym cokole. Wybudowana została z kamienia przeszło trzysta lat temu. Na szczycie figury umieszczona jest kamienna kula z metalowym krzyżem. Umieszczony na figurze oryginalny, staropolski tekst jest trudny do odczytania. Wyrazy są łączone, nie ma znaków interpunkcyjnych, trzeba składać literkę po literce. Ja ten tekst odczytałam tak: „D.O.M. Tu Jakub Ruszczyk, opętany, lat 24, usłyszał głos pański – Postaw tu figurę dla chwały syna mego, a na znak tego jesteś uzdrowiony. Ten cud stał się około roku 1646”. Nieco niżej, pod tym tekstem, widnieje kolejny tekst napisany staropolskim językiem, na którym czytamy: „Tu jasności niebieskie, tu procesje anielskie widzieć tu śpiewanie owych zagłuszane były. Więc na pamiątkę tego i wy pani Rozalia Zdzieduszyc łaskawa tę wystawiła kolumnę, za którą, kto czytasz, zmów Zdrowaś Mario”. Ta przykościelna figura jest jedną z najstarszych zachowanych w Krasnobrodzie figur.
Kościół z lewej strony łączy się z klasztorem (dawniej zakonu dominikanów, obecnie księża diecezjalni sprawują opiekę nad klasztorem). Na dolnym korytarzu klasztoru znajduje się „Wystawa z Ziemi Świętej” oraz Muzeum Sakralne, gdzie można zobaczyć m.in.: mszały, kielichy, kolekcje szat liturgicznych oraz kolekcję starodruków pochodzących z archiwum parafialnego. Na piętrze klasztoru warto zobaczyć „Wystawę Maryjną” przedstawiającą Sanktuaria Maryjne w Polsce. Przed klasztorem znajdują się współczesne, wykonane z kamienia pomniki: Chrystusa Dobrego Pasterza i Papieża Jana Pawła II. Wykonał je miejscowy artysta rzeźbiarz Andrzej Gontarz.
Obecnie krasnobrodzkie Sanktuarium pw. Nawiedzenia Najświętszej Marii Panny jest głównym Sanktuarium Diecezji Zamojsko – Lubaczowskiej.
