The church was built between 1855 and 1857, replacing an earlier temporary chapel, under the direction of master builder G. Svensson from Piteå. Constructed in timber, it was designed in the shape of a cross, a plan still evident in the building's layout today. The reported building cost was 1000 Rdr Banco.
Originally the church had a shingled roof, replaced in 1882 by one of roofing felt, and later, in 1934, by tiles, when the tower was also clad in copper sheeting. During restoration work in 1913–1914 a sacristy was added at the eastern transept, and the altar, which had originally stood in the corner between the southern and eastern transepts, was moved to the eastern transept at this time. A porch was added at the western transept in 1970.
The church's first organ, situated in the south transept, was built by Olof Andersson of Bjurträsk, Norsjö, a detail that gives a sense of the church's early rural craftsmanship and local connections.
Before Österjörns kyrka was built, worship in the area took place in an earlier chapel, later converted into a parish hall, which has since been demolished. The parish itself has a longer history, having formed part of Norsjö pastorate before becoming a chapel congregation under Norsjö in 1848 and an independent pastorate in 1892.