Á útmánuðum 1862 var hafist handa við að byggja kirkju á Akureyri, en áður höfðu Akureyringar átt kirkjusókn að Hrafnagili. Kirkjusmiðurinn Jón Chr. Stephánsson segir að byrjað hafi verið að reisa kirkjuna þann 26. maí 1862 (þ.e. reisa sperrur) og var hún reist þar sem nú er Minjasafnskirkjan.
Reisugildi var haldið 28. maí 1862, miðvikudaginn fyrir uppstigningardag, með pompi og prakt. Í Norðanfara segir svo um þann atburð:
„Fagnaðarveifa var á hverri stöng og siglutré, fallbyssunum var skotið, svo að bergmálaði í fjöllunum, ekki samt í Tindastól, blómkrans festur upp í grindina, gleðiópin hljómuðu, staupin klingdu full af hinum gleðjandi og hressandi lög, sem optast verður að vera annarsvegar, þá mikið er um dýrðir og samkoma manna á að vera sem yndælust og minnilegust; en oss virðist sem Bachus ætti hvergi að koma nærri við slík tækifæri ...“
Fjármuni skorti til að ljúka kirkjusmíðinni að innan, en með styrkjum frá bæjarbúum og lántökum hjá Möðruvallaklausturskirkju og verslunarstjórunum Eðvald Möller og Páli Th. Johnsen tókst að klára bygginguna. Hún var byggð af stórhug og rúmaði því sem næst 300 manns. Kirkjan var vígð af sr. Daníel Halldórssyni prófasti 28. júní 1863.
Turn var austan á kirkjunni, hneykslaði það marga og gekk þvert á kirkjulega venju, þó var inngangurinn að vestan. Við endurbætur og lagfæringar sem lokið var um áramót 1879-1880 var turninum og fleiru breytt og hann settur vestan á kirkjuna.
Akureyrarkirkja eftir breytinguna 1879
Þegar kirkjan var rifin veturinn 1942-1943 fannst skjal, sem Jón Chr. yfirsmiður hafði ritað, í blikkdós undir gólffjölunum og er það eins konar hornsteinsskjal með upplýsingum um bygginguna, skjalið er dagsett 24. apríl 1863 og er varðveitt á Héraðsskjalasafninu á Akureyri,sjá hér.