Kaldestad var eget sogn i middelalderen. Erlend, sogneprest til Kaldestad, nevnes i et diplom fra 1337 (DN I,249), og Kallestaa sokn i et diplom fra 1342 (DN XXI, 66). Kirken er også nevnt i registeret, Bergens kalvskinn (s.7). Den lå på gården Kaldestad. Denne gården var delt i to bruk. Øvre Kaldestad var i 1647 kapittelgods, mens nedre Kaldestad ble eid av prestebordet i Kvinnherad. Opprinnelig var antakelig dette bruket prestegård for presten til Kaldestad. Kirken lå like i nærheten av det gamle tunet. Middelalderkirken† var etter alt å dømme en stavkirke. Kirken kalles allerede i 1600-årene for Husnes kirke. Husnes er også navnet på sognet og prestegjeldet som ble opprettet i 1967. Før den tid lå Husnes sogn under Kvinnherad prestegjeld. Husnes prestegjeld omfatter foruten hovedsognet Holmedal og Valen sogn som ble overført fra henholdsvis Skånevik og Fjelberg prestegjeld i 1967.
Tegninger til kirken ble først utarbeidet av cand.theol. Andreas Grønning, men kirken ble bygget etter tegninger utført av J. Utne (Minneskrift). Byggmester var Askjell Aase. Kirken ble innviet 11. september 1874.
I 1960 ble den istandsatt etter planer utarbeidet av arkitektene T. Alvsaker og E. Vaardal Lunde. Fargerestaurering ble utført av maleren Johannes E. Rørvik. I 1974 ble kirken ombygget etter planer utarbeidet av arkitekt Peter Helland-Hansen.