Pierwsza wzmianka o parafii w Kamiannej pochodzi z 1637 r., kiedy to biskup Jakub Zadzik ustanowił tutaj parafię greckokatolicką i przydzielił do niej ks. Piotra Przysłupskiego. W tym czasie powstała prawdopodobnie pierwsza cerkiew. Kolejna zbudowana była w 1805 r., remontowana w 1892 r. Od lat 30. XX w. praktycznie nieużytkowana, gdyż mieszkańcy w większości przeszli na prawosławie i zbudowali nową cerkiew. Polscy mieszkańcy, którzy przybyli tu po roku 1947 adaptowali na kościół dawną cerkiew prawosławną, a tę przeniesiono w 1949 r. do nowopowstałej parafii w Bukowcu. Pierwotny kształt cerkwi R. Brykowski zaliczał do typu łemkowskiego, schyłkowego. Była dwudzielna, nakryta dachami kalenicowymi z wieżą o pochyłych ścianach, zwieńczoną izbicą. Prezbiterium i nawa nakryte były beczkowymi sklepieniami zrębowymi, spotykanymi w cerkwiach Rusi Zakarpackiej i Rumunii. Podczas remontu w 1892 r. bryła cerkwi wydłużyła się - dobudowano nowe prezbiterium z dużą zakrystią od północy a stare prezbiterium włączono do nawy, pozostawiając na zewnątrz dwie linie kalenic. W efekcie powstały trzy linie kalenic, bo dobudowane, nowe prezbiterium jest niższe od poprzedniego. Wieża, nawa i nowe prezbiterium zwieńczone zostały banistymi hełmami z makowiczkami i krzyżami żelaznymi.