Obecny kościół parafialny - najstarsza świątynia na terenie Bieszczadów - został wymurowany z kamienia, na planie krzyża, z dwoma kaplicami tworzącymi jego ramiona i wieżą od pn.-zach., w stylu póżnogotyckim, około 1539 r. Fundatorem był Piotr Kmita, marszałek wielki koronny, kasztelan sandomierski, wojewoda sandomierski i krakowski, właściciel miasta Leska. Uroczystośc poświęcenia nowego kościoła odbyła się w pierwszą niedzielę po Wszystkich Świętych w 1539r. Początkowo kościół parafialny w Lesku był pod wezwaniem św. Mikołaja, a od XVII w. pod wezwaniem Nawiedzenia Najświętszej Maryi Panny.
Z XVI wieku zachowały się m. in.:
* kondygnacje na zewnątrz wieży po dach;
* wykuta w kamieniu nad wejściem od zewnątrz tarcza z herbem Śreniawa Kmitów;
* sklepienia póżnogotyckie w kaplicach;
* renesansowe portale kamienne - przy wejściu do zakrystii oraz w murze otaczajęcym kościół od północnego zachodu;
* okna zamknięte półkoliście z gzymsem podokiennym.
Z pierwszej połowy XVIII wieku pochodzi: - chór (przebudowany w latach 1899-1900); - chrzcielnica - barokowa z czarnego marmuru, w kształcie kielicha, puklowana z drewnianą pokrywą; - ambona (1754r.) póżnobarokowa z ornamentami i rzeżbami rokokowymi, wykonana z drewna. Cztery większe rzeżby zdobiące ambonę, to święci: Ambroży, Grzegorz Wielki, Hieronim i Augustyn. Zaplecek z tablicami przykazań jest ujęty kotarą podtrzymywaną przez aniołki. Dwukondygnacyjny baldachim zwieńczony rzeżbami Boga Ojca, aniołków i postaci w zbrojach antycznych oraz Ducha Świętego w postaci gołębicy w glorii.
Z II połowy XIX w. pochodzi rzeźba Matki Bożej z Dzieciątkiem na kolumnie (obok ołtarza bocznego w nawie głownej) wykonana z białego marmuru przez Włocha F. Bertiniego.
23 sierpnia 1704r. Szwedzi podpalili Lesko. Wówczas na kościele spłonął dach kryty gontem. Przedtem kościół został ograbiony. Około połowy XVIII wieku Gotfryd Hoffman, architekt śląski przebudował wnętrze (w stylu późnobarokowym) i nieco podniósł jej mury. W 1760r. biskup przemyski Wacław Hieronim Sierakowski dokonał powtórnej konsekracji kościoła. W 1889 roku nadbudowano wieżę kościelną która przybrała wygląd neoromański. Dach został pokryty blachą.
Ołtarz główny (z 1770 roku) późnobarokowy z ornamentami i rzeźbami rokokowymi z czterema kolumnami i dwiema pólkolumnami na cokołach, z rzeźbami świętych męczenników biskupów Stanisława i Wojciecha oraz aniołów w zwieńczeniu. W polu głównym znajduje się obraz Grupa Pasji (widoczny w czasie Wielkiego Postu). W pozostałych okresach roku liturgicznego odsłaniany jest obraz Matki Bożej Różańcowej (z II połowy XX w.). W zwieńczeniu ołtarza znajduje się obraz Nawiedzenia Najświętszej Maryi Panny (z I połowy XIX w.)
Ołtarz św. Antoniego Pustelnika (w kaplicy południowo-zachodniej) ufundowany w połowie XIX w.; klasycystyczny, z czterema kolumnmi (odnowiony w 2004r.). W polu głównym znajduje się obaz św. Antoniego Pustelnika, pod ołtarzem, antependium w kształcie groty z rzeźbami: leżącej postaci świętego Antoniego i dwóch lwów. Na ścianie wschodniej obraz świętych pustelników Antoniego i Pawła z Teb. Na ścianie zachodniej portret o. Józefa Gracjana Piotrowskiego, pijara znanego w literaturze polskiej satyryka i publicysty, proboszcza leskiej parafii latach 1783-1785 (jego doczesne szczątki spoczywają w podziemiach kościoła). W podziemiach kaplicy spoczywają rotmistrz Franciszek Pułaski, stryjeczny brat Kazimierza- konfederat barski, zmarły na zamku leskim 16.08.1769 r. na skutek ran otrzymanych w bitwie z Rosjanami pod Hoszowem koło Ustrzyk Dolnych. W 1869 r. Edmund hrabia z Siecina Krasicki ufundował w kaplicy św. Antoniego epitafium inskrypcyjne poświęcone Franciszkowi Pułaskiemu, wykonane przez Antoniego Galliego, mistrza sztuki rzeźbiarskiej i kamieniarskiej z Krakowa.
Ołtarz boczny w nawie głównej, styl pseudoklasyczny, z dużą figurą Matki Bożej Niepokalanej oraz obrazem, przesłanoiającym figurrę.: Matka Boża wręcza różaniec św. Dominikowi, obok klęczy św. Katarzyna Sieneńska (w 1878r. był tu ołtarz Matki Bożej Różańcowej, kóry w 1906 został rozebrany a w jego miejsce poświęcony nowy- istniejący obecnie).
Ołtarz Najświętszego Serca Pana Jezusa (w kaplicy północno-wschodniej), sprowadzony z Francji (pierwsza wzmianka o nim pochodzi z 1925r.). W ołtarzu znajduje się duża płaskorzeźba postaci Chrystusa oraz dwie mniejsze, świętych apostołów Piotra i Pawła. Ołtarz ten zwany "kołkowym" posiada konstrukcję bez gwoździ.
W latach 1937-1938 wnętrze kościoła zostało odmalowane przez słynnego artystę lwowskiego prof. Jana Henryka Rosena, który m.in. wykonał malowidła ścienne w katedrze ormiańskiej we Lwowie i w kaplicy w Castel Gandolfo. Dzięki Rosenowi kościól w Lesku otrzymał otrzymał nową polichromię, a w prezbiterium (na ścianie nad drzwiami do zakrystii i ławką kolatorską) dwa obrazy: "Chrystus na morzu" i "Hołd Maryi" (do tego obrazu pozowały podobno osoby z Leska). Prof. Rosen namalował także (na ścianie nad chórem) herby wszystkich kolatorów (dobroczyńców) leskiego kościoła: Kmitów (do 1579r.), Stadnickich i Barzych (1580-1594), Stadnickich (1594-1731), Ossolińskich (1731-1769), Mniszchów (1769-1799) i Krasickich z Siecina (1799-1944).
W świątyni znajdują się epitafia inskrypcyjne z czarnego marmuru, m.in. Teresy ze Stadnickich Ossolińska, wojewodzina wołyńska (zm. 1776) i Józefa Ossolńskiego, wojewody wołyńskiego (zm. 1780) - z XVIII; Edmunda hr. Krasickiego uczestnika Powstania Listopadowego, organizatora i dowódcy Gwardii Narodowej w Lesku, marszałka powiatu leskiego (zm. 1894) oraz jego żony Marii Anieli z Brzostowkich-Krasickiej (zm. 1908) - z początku XIX w.
Przy wejściu do kościoła po lewej stronie, po II wojnie światowej umieszczono fragmenty ołtarza pochodzącego z wiejskiej bieszczadzkiej cerkwi, opuszczonej po wysiedleniu Ukraińców . Na ścianie po prawej stronie znajduje się ufundowana w 1978 r., z okazji 500-lecie istnienia leskiej parafii, pamiątkowa tablica z imionami i nazwiskami wszystkich proboszczów parafii oraz tablica upamiętniająca ks. Ludwika Palucha, leskiego proboszcza z czasów II wojny światowej.
Dzwonnica wymurowana na planie kwadratu, późnobarokowa. Jej budowa trwała od 1725 r. do lat sześcdziesiętych XVIII wieku. W cześniej dwa dzwony i sygnaturka znajdowały się w wieży kościoła. W czasie pożaru w 1840 r. dzwony te uległy zniszczeniu. W 1914 r. nowe dzwony zagrabili Austriacy. Obecnie w dzwonnicy znajdują się cztery dzwony: duży - "Królowa Polski" (z 1925 r); średni, ufundowany na pamiątkę Odrodzenia Polski "św.Ignacy" (z 1924 r.); "św. Antoni" (z 1922 r.) oraz mały bez imienia (z 1925 r.).
W 1550 r. rozpoczęto budowę muru otaczającego cmentarz znajdujący sie przy kościele. Mur z cegły został pokryty gontami. W tym czasie kościół wraz z otoczeniem, położony na obwodzie zabudowy miasta, przylegający do zbudowanych w XII wieku wałów, stanowił bastion obronny. W 1925 r. nadbudowano mur od dzwonnicy wzdłuż ul. Kościuszki aż do końca i przykryto go dachem. W 1933 r. ogrodzono brzeg od strony północno-zachodniej.