The timber church was built in 1836 using nearby Gideå kyrka as a model, with a nave, an eastern chancel and a western tower. According to church sources, the building was only completed in its present form in 1882, during the reign of Oscar II, when a tower was added; the parish records from that time name the bishop, rural dean, vicar and chapel preacher then serving.
The altarpiece, painted by the decorative artist Charles Bylander, was inaugurated on Easter Sunday 1910. It is a copy of an altarpiece in Molde kyrka in Norway, and was donated by a local merchant in memory of his wife.
The pulpit is said, according to an old account, to be older than the church itself. An inventory drawn up in November 1919 describes two surviving parts of a pulpit from around 1700, recording that a pulpit had been given to Trehörningsjö in 1862 from Nordmaling (Arnäs) church; other pulpit sections were said to have been acquired by Nordiska museet from a local resident. The exact history and completeness of the present pulpit is not entirely clear from these accounts.
The font, carved from Gotland sandstone with biblical symbols, was designed by the architect Einar Lundberg and donated in 1930 by the sculptor N.A. Sandin, a native of Trehörningsjö; the matching baptismal bowl dates from the same year.
The church also has an organ built in 1954 by the Setterquist workshop, a modest instrument typical of many rural Swedish churches of its period.