Kościół św. Justyny jest drugim kościołem wzniesionym w Paleśnicy. Pierwszy nieistniejący kościół drewniany pw. św. Klemensa był postawiony na miejscu starego cmentarza. Obecna świątynia fundacji hr. Justyny Lanckorońskiej, dziedziczki dóbr melsztyńskich została wzniesiona w 1808 r. i konsekrowana 20 lat później przez bpa tarnowskiego Grzegorza Tomasza Zieglera.
Kościół zbudowany jest z kamienia, otynkowany, jednonawowy z dobudowanymi z boku nawy kaplicą i kruchtą. Wieża przyległa od zachodu do nawy. Wzniesiona jest na planie kwadratu, trójkondygnacyjna i nakryta czterospadowym dachem zwieńczonym czteroboczną nadstawką. Nad dwuspadowym siodłowym dachem nawy wznosi się wieżyczka na sygnaturkę z latarnią.
Wyposażenie świątyni to między innymi: ołtarz główny z 1895 r. z obrazami św. Klemensa i Matki Bożej Nieustającej Pomocy, ołtarze boczne, ambona z 1895 r. obraz fundatorki świątyni Justyny lanckorońskiej z 1904 r. oraz organy wykonane w 1901 roku.
Obok świątyni wolno stojąca metalowa dzwonnica przykryta dwuspadowym dachem. Zawieszone na dzwonnicy dzwony odlane zostały w 1955 r.