The building's origins lie in the growth of the Södra Svartbyn housing area during the 1960s and 1970s, which created a need for both church activities and a municipal youth centre. Boden Municipality and Överluleå parish agreed to combine these needs in a single building, known as Torpgärdangården, built between 1976 and 1977 and inaugurated on 30 September 1977.
By the 1980s, it became clear that the different community and church activities sometimes interfered with one another, and discussions began about dividing the building. This separation between the municipality and the parish took place in spring 1994.
In 1996, Bishop Rune Backlund consecrated the church premises, which were then given the name Matteuskyrkan, a reference to the biblical assurance that where people gather in Christ's name, he is present among them.
A church bell was donated to Matteuskyrkan in 2000 by one of the congregation's volunteer groups; it had previously stood in Notviken. In spring 2003, the interior of the church hall took on its present appearance, following a renovation that included artistic decoration by Marianne Öqvist of Luleå.