Pierwszy drewniany kościół pod wezwaniem Świętego Ducha z lat siedemdziesiątych XV wieku znajdował się w sąsiedztwie ówczesnego szpitala dla kalek i ubogich (obecnie Gimnazjum przy ul. Kościuszki). Początkowo spełniał rolę kościoła parafialnego, a później szpitalnego; nieremontowany, w XVII wieku uległ zniszczeniu.
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ść poświęcenia nowego kościoła odbyła się w pierwszą niedzielę po Wszystkich Świętych w 1539 r. 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.
Na uwagę zasługuje ambona (1754 r.) 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.
Barokowa chrzcielnica w kształcie kielicha, znajdująca się w leskiej świątyni, została wykonana czarnego marmuru, puklowana z drewnianą pokrywą.
Z II połowy XIX w. pochodzi rzeźba Matki Bożej z Dzieciątkiem na kolumnie (obok ołtarza bocznego w nawie głównej) wykonana z białego marmuru przez Włocha F. Bertiniego.
Ołtarz główny (z 1770 roku) późnobarokowy z ornamentami i rzeźbami rokokowymi z czterema kolumnami i dwiema półkolumnami na cokołach, z rzeźbami świętych męczenników biskupów Wojciecha i Stanisława 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 kolumnami (odnowiony w 2004r.). W polu głównym znajduje się obraz ś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.
Ołtarz boczny w nawie głównej, styl pseudoklasyczny, z dużą figurą Matki Bożej Niepokalanej oraz obrazem, przesłaniającym figurę.: 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, któ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 podziemiach kościoła spoczywają: o. Józef Gracjan Piotrowski, pijar – znany w literaturze polskiej satyryk i publicysta, proboszcz leskiej parafii latach 1783-1785, 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.
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.
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ą. W 2009 roku dokonano kapitalnego remontu więźby dachowej oraz starą blachę wymieniono na nową – miedzianą.
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ół w Lesku 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).
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śćdziesiątych XVIII wieku. Wcześ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.);
- mały bez imienia (z 1925 r.).
W 1550 r. rozpoczęto budowę muru otaczającego cmentarz znajdujący się 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 XVII 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.