Jak podaje legenda, w miejscu gdzie dzisiaj stoi kościół, miała niegdyś mieścić się pustelnia Katarzyny, siostry świętych pustelników - Świerada, Justa i Urbana, którzy osiedli w dolinie Dunajca. Inna opowieść głosi, że w tym miejscu objawił się obraz świętej Katarzyny, który siostry Klaryski ze Starego Sącza bezskutecznie przenosiły do swojego klasztoru, a obraz w cudowny sposób wracał w pierwotne miejsce. Obraz ten do dziś znajduje się w głównym ołtarzu.

Historyk Jan Długosz wspomina o parafii w Kamionce wraz z jej kościółkiem w swym dziele „Liber Beneficiorum” trzykrotnie. Z tych zapisów wynika, że około 1440 roku istniała parafia wraz z drewnianym kościółkiem, która w 1470 roku utraciła swoją odrębność i została przyłączona do parafii w Ujanowicach. W tym czasie drewniany kościół świętej Katarzyny w Kamionce znacznie podupadł. Na początku XVIII wieku groził kompletną ruiną i dlatego rozpoczęto jego przebudowę (a być może wzniesiono go od nowa wykorzystując materiał z poprzedniego kościółka).

Wewnątrz kościoła świętej Katarzyny znajduje się między innymi krucyfiks z około 1470 roku na belce tęczowej, w ołtarzu głównym XVII-wieczny barokowy posążek świętej Katarzyny oraz obrazy patronki świątyni i Matki Boskiej. Ciekawa jest również ambona z przedstawieniami ewangelistów. Wnętrze świątyni zdobi polichromia figuralna z 1857 roku.

Obiekt znajduje się na Szlaku Architektury Drewnianej.