Keldnakirkja er í Oddaprestakalli í Rangárvallaprófastsdæmi. Keldur voru í Keldnaþingum, sem voru 
1880 og samtímis var sóknin færð að Odda. Katólskar kirkjur voru helgaðar Páli postula. Járnvarin timburkirkja, sem nú stendur þar, var byggð 1875. Frumkvöðull byggingar hennar var Guðmundur Brynjólfsson, bóndi á Keldum, og yfirsmiður var Halldór Björnsson frá Felli í Mýrdal. Kirkjan er fremur lítil, enda er söfnuðurinn lítill.
Gert var við kirkjuna á árunum 1956-57. Þá var steyptur grunnur undir hana og henni lyft og settir voru steindir gluggar í hana. Gréta og Jón Björnsson skreyttu og máluðu kirkjuna. Hjörtur Oddsson, snikkari og bóndi í Eystri-Kirkjubæ, smíðaði prédikunarstólinn, altarið og ljósaarma og ártalið 1875, þegar kirkjan var byggð. Eldri altaristafla (Kvöldmáltíðin; Ámundi Jónsson, snikkari í Syðra-Langholti), frá 1792 er þar líka, auk nýrrar (eftir danskan málara), sem ber heitið Eitt er nauðsynlegt. Á hliðarveggjum eru 15 vegglampar úr birki, sem Elías Tómasson á Uppsölum í Hvolhreppi smíðaði. Báðum megin altaristöflunnar hanga tvö líkneski úr katólskri tíð. Þau tákna Maríu guðsmóður með Jesúbarnið og Pál postula. Tvíarma koparstjaki úr kopar er kominn úr Leirubakkakirkju í Landssveit, sem var lögð niður 1765. Oblátuöskurnar úr tré eru gamlar, svo og kaleikurinn, patínan og eirskírnarfatið. Klukkurnar þrjár eru frá árunum 1523, 1583 og 1602.
