A church at Hällesjö is documented as far back as 1314, when the parish, then known as Rotakyl (with several variant spellings), appears in records of a tax paid to Uppsala. Hällesjö and neighbouring Håsjö were together known locally as Kälarne, an old name for the wider district that has persisted alongside the parish names.
The medieval predecessor to today's church stood just north of the current building and was a simple stone structure with wooden gable tops, lacking a chancel, sacristy or porch. It had only fourteen small pews, each allocated to a particular family, while children and boys were expected to stand. This older church was demolished in 1873, apparently because the parish could not justify maintaining two churches once the new one was built; some researchers suggest an even earlier timber chapel may have preceded the stone church.
Several furnishings from the old church survive. An altarpiece bought in Hudiksvall in 1686 and brought to Hällesjö by horse and sledge can now be seen beneath the gallery on the north wall. A sixteenth-century triumphal crucifix, an old censer and an image of St Rochus, traditionally invoked against plague, were also part of the medieval church's furnishings, though St Rochus and a seventeenth-century carved pulpit are now held at the county museum rather than in the church itself. An eighteenth-century altar arrangement, said to resemble one at Frösö church, is kept in the parish hall.dinated.
The present stone church, an octagonal building with a chancel to the south and porch to the north, was built in 1847–1848 to designs by the architect Johan Adolf Hawerman and consecrated in 1853. Its pulpit dates from the year of building, and the organ, installed in 1935, retains a case from 1850 belonging to an earlier instrument.
Standing apart from the church, the striking wooden bell tower on the churchyard hill was raised in 1781 by the master builder Pål Persson, whose octagonal towers with onion-shaped domes are a recognisable feature of the region; a companion tower of his at Håsjö is often described as the neater of the two, while Hällesjö's is considered the more imposing. An inventory from 1689 shows that an earlier tower and bell already existed on the site before Persson's construction.