Valtimon kirkko on valmistunut vuonna 1901 ja vihitty käyttöönsä 25.8.1907. Rakennuspiirustukset laati A.E. Ollilainen. Sisätilojen nykyilmeen kirkko sai arkkitehti Kauno S. Kallion jodolla toteutetussa peruskorjauksessa vuonna 1931.

Alttaritaulu, joka esittää Kristusta ristillä, on enolaisen Eino J. Härkösen maalaama vuodelta 1931. Kirkossa on kaikkiaan 34 eri kuva-aihetta ja reliefiä. Evankelistoja kuvaavat reliefit ovat J.O. Raja-ahon tekemiä ja muut kuvat, alttaritaulua lukuunottamatta, ovat Urho Lehtisen käsialaa.

Kirkossa on 32-äänikertaiset Aarne Wegeliuksen ja Kangasalan urkutehtaan rakentamat täyspneumaattiset urut.