Iisalmen kirkkopitäjä on muodostettu 1620 Kuopion emäseurakunnan pohjoisosista. Aluksi se käsitti koko Ylä-Savon alueet, mutta myöhemmin siitä on erotettu kappeleiksi nykyiset Kiuruveden, Lapinlahden, Pielaveden, Sonkajärven ja Vieremän seurakunnat.[2]
Iisalmen Kustaa Adolfin kirkko eli Iisalmen vanha kirkko on seurakunnan kolmas kirkkorakennus. Ensimmäinen tuhoutui tulipalossa 1700 ja toinen, muodoltaan ristikirkko, purettiin huonon kuntonsa vuoksi nykyisen kirkon valmistuttua.[2]
Puista kirkkoa varten saatiin piirustukset Tukholman yli-intendentinvirastosta ja vuonna 1778 aloitetut rakennustyöt tehtiin kalajokelaisen kirkonrakentaja-rakennusmestari Simon Jylkkä-Silvénin johdolla vuosina 1779–1780.[3] Kirkko vihittiin käyttöön 5. maaliskuuta 1780.
Kellotapuliin kiinnitetyn Kustaa Adolfin kirkkojen muistolaatan mukaan kellotapuli on vuodelta 1700. Kellotapuli on toisen lähteen mukaan vasta 1700-luvun puolivälistä, mutta tarkkaa rakentamisvuotta ei tiedetä. Vuonna 1752 tapuli tervattiin rakennusmestari Anders Brovallin johdolla, ja Mikael Toppelius maalasi sen vuonna 1756.[4]
Kirkkoa on kunnostettu useaan otteeseen. Vuonna 1876 kirkkoa kunnostettiin sisä- ja ulkoarkkitehtuuriltaan ja sisustukseltaan arkkitehti F. A. Sjöströmin laatiman ehdotuksen mukaisesti, jolloin muun muassa sisäholvi purettiin. Vuonna 1927 kirkkoa muutettiin ja sisustusta uusittiin Rafael Blomstedtin suunnitelmien mukaan.[5] Sen jälkeen kirkossa tehdyt muutokset ovat vähäiset.[2]
Kirkon pohjoispuolella sijainnut kirkkoherranpappila siirrettiin HelsinginSeurasaaren ulkomuseoon. Pappilasta jäi jäljelle koivukuja ja suuri kivinavetta.