Cisna była wzmiankowana już w 1497 roku należąca do dóbr Balów w Hoczwi[2].
W 1914 roku w Cisnej istniała już kaplica mszalna pw. Matki Bożej Częstochowskiej, do której czasowo dojeżdżali kapłani z Baligrodu. Z powodu zwiększonej liczby wiernych postanowiono zbudować większy kościół. W 1912 roku podjęto decyzję o budowie murowanego kościoła. Budowa trwała z przerwą wojenną do 1922 roku. 26 grudnia 1925 roku ks. Stanisław Bałuk, proboszcz z Baligrodu poświęcił kościół filialny pw. św. Stanisława Biskupa. W 1931 roku zbudowano plebanię, ale w 1932 roku urządzono w nim szkołę. Z powodu dalekiej odległości od parafii proboszcz przyjeżdżał do Cisnej tylko raz w miesiącu. Miejscowi katolicy uczestniczyli także w nabożeństwach w cerkwi. W 1939 roku przez kilka miesięcy przebywał w Cisnej ks. Józef Chmurowicz. W 1941 roku przybył ks. Ludwik Bartmiński, który w 1944 roku opuścił wiernych przed nadejściem frontu. W czasie wojny kościół był poważnie zniszczony, a liczba ludności wsi zmniejszyła się trzykrotnie[3].
2 sierpnia 1958 roku dekretem bpa Franciszka Bardy została erygowana ekspozytura, z wydzielonego terytorium parafii w Baligrodzie. W skład parafii weszły miejscowości: Cisna, Dołżyca, Krzywe, Przysłup, Kalnica Górna, Smerek, Wetlina, Łopienka, Habkowce, Jabłonki, Majdan, Liszna, Roztoki Górne, Żubracze. W 1968 roku do kościoła dobudowano drugą zakrystię[4].
21 czerwca 1997 roku w Przysłupie abp Józef Michalik poświęcił plac pod budowę kościoła filialnego. 26 lipca 1998 roku abp Józef Michalik poświęcił kościół pw. Wszystkich Świętych[11].