Pierwsza drewniana świątynia pod wezwaniem Świętego Ducha z lat 70. XV w. zlokalizowana w pobliżu obecnego gimnazjum przy ul. Kościuszki. Przez dłuższy czas nie remontowany, w XVII w. ulega zniszczeniu. Obecny kościół został wybudowany w roku 1539 w stylu późnogotyckim. Jego fundatorem był Piotr Kmita, ówczesny właściciel miasta. Jest to najstarsza świątynia na terenie Bieszczadów. Poświęcono ją po dniu Wszystkich Świętych w 1519 roku. Do XVII w. funkcjonowała pod wezwaniem św. Mikołaja, potem pw. Nawiedzenia Najświętszej Maryi Panny.
Na wyposażeniu znajduje się chrzcielnica barokowa z czarnego marmuru. Ambona z 1754 r. z drewna. Postacie świętych: Ambrożego, Grzegorza Wielkiego, Hieronima i Augustyna wyrzeźbione w drewnie zdobią to późnobarokowe dzieło. Ołtarz główny z 1770 r. również późnobarokowy, zdobiony ornamentami i rzeźbami z czterema kolumnami i półkolumnami na cokołach. Figury świętych biskupów Wojciecha i Stanisława dopełniają całości. W centrum znajduje się obraz "Grupa Pasji" (odsłaniany w czasie Wielkiego Postu). Ołtarz zwieńcza obraz Nawiedzenia N. M. P. (z połowy XIX w.). Ołtarz boczny w nawie głównej świątyni w stylu pseudoklasycznym z figurą Matki Bożej Różańcowej (w 1906 r. rozebrany) a w jego miejsce poświęcony nowy - istniejący obecnie.
Nad wejściem do kościoła znajduje się herb Kmitów. Dwa ołtarze znajdują się w kaplicach: południowo - zachodniej i północno - wschodniej. Pierwszy to ołtarz św. Antoniego Pustelnika oraz ołtarz Najświętszego Serca Pana Jezusa. Jest to konstrukcja bez gwoździ.
Znajdują się także w świątyni epitafia i inskrypcje z czarnego marmuru m. in. Teresy ze Stadnickich Ossolińska - wojewodzina wołyńska (zm. 1776 r. 0 i Józefa Ossolińskiego - wojewody wołyńskiego ( zm. 1780 r.), Edmunda hr. Krasickiego, uczestnika Powstania Listopadowego i dowódcy Gwardii Narodowej w Lesku, marszałka powiatu leskiego (zm. 1894 r.) oraz jego żony Marii Anieli z Brzostowskich - Krasickiej (zm. 1908 r.).
Po pożarze wzniesionym latem 1704 r. przez Szwedów w Lesku spłonął dach kryty gontem. Oczywiście przedtem został przez nich ograbiony i splądrowany. W połowie XVIII w. architekt śląski Gotfryd Hoffman przebudował wnętrze świątyni (późny barok). Dach pokryto blachą. W końcu lat 80 XIX w. została nadbudowana wieża kościelna. Po upływie wieku w 2009 r. wyremontowano więźbę dachową oraz wymieniono blachę na nową.
W końcu lat 30. XX w. prof Jan Henryk Rosen, słynny artysta lwowski odmalował wnętrze. Kościół wzbogacił się o nową polichromię i nowe obrazy: "Chrystus na morzu" oraz "Hołd Maryi". Jan Henryk Rosen uwiecznił także herby wszystkich dobroczyńców kościoła: Kmitów ( do 1579 r. ), Stadnickich i Barzych (1580 - 1594), Stadnickich (1594 - 1731), Ossolińskich (1731 - 1769), Mniszchów (1769 - 1799) i Krasickich z Siecina (1799 - 1914).
Od połowy XVI w. budowa muru otaczającego cmentarz znajdujący się przy kościele. W tamtych latach był położony na obwodzie miasta. Przylegający do zbudowanych wałów stanowił bastion obronny.
W kruchcie znajduje się ufundowana w 1978 r. pamiątkowa tablica z okazji 500 - lecia istnienia leskiej parafii z imionami i nazwiskami wszystkich proboszczów oraz tablica upamiętniająca ks. Ludwika Palucha, proboszcza z czasów okupacji. Podziemia kościoła kryją zwłoki o. Józefa Gracjana Piotrowskiego, Pijar - znany publicysta i satyryk, proboszcz parafii w latach 1783 - 1785 oraz rotmistrza Franciszka Pułaskiego, konfederata barskiego, zmarłego na zamku leskim 16. 08. 1769 r.
Dzwonnica - późnobarokowa budowana w latach 1725 - 1760. Dwa dzwony: sygnaturka uległa zniszczeniu wskutek pożaru w 1840 r. W 1914 r. Austriacy zagrabili nowe dzwony. Obecnie znajdują się w niej 4 dzwony. Jeden duży "Królowa Polski" (1925 r.), średni "św. Ignacy" (1924 r.), "św. Antoni" (1922 r.) i mały bez imienia (1925 r.).