1946 m. Panevėžio vyskupas nurodė, kad nėra aiškių žinių, kada atsirado pirmoji bažnyčia. Vieni mano, kad ji buvo įkurta 1390 m., kiti – kad ji įsteigta Vytauto 1416 m. Išlikę bažnyčios inventoriai aprašinėja tik priešpaskutinę bažnyčią, pastatytą 1802 m., tačiau ją 1879 m. sunaikino gaisras, ir su ja žuvo ankstesni dokumentai. Bažnyčios fundatoriais buvo Lietuvos didieji kunigaikščiai. Jie skirdavo ir Utenos bažnyčiai klebonus. 1608 m. sausio mėn. Utenos klebonu skiriamas Merkelis Saladzevičius. 1662 m. klebonavo Motiejus Survila, Vendeno kanauninkas, bažnyčiai paaukojęs komuninę. 1685 m. Utenos ir Užpalių klebonu buvo Mykolas Puzyna. Bažnyčia buvo sena, medinė, Šv. Kryžiaus vardo. 1698 m. Utenos bažnyčiai jis paaukojo sidabrinę monstranciją, kuri 1807 m. buvo perdirbta į paprastą kryžių, šiandien stovintį Kryžiaus altoriuje.

1796 m. pradedama statyti nauja medinė bažnyčia, kuri užbaigiama 1802 m. 1849 m. Utenos parapija, buvusi Vilniaus vyskupijos ribose, buvo priskirta Žemaičių vyskupijai. 1879 m. medinė Utenos bažnyčia sudegė. 1884 m. buvo sumūryta nauja bažnyčia. Bažnyčia istoristinė, graikiško kryžiaus plano, dvibokštė, su kupolu, penkiasiene presbiterija, pusapskritėmis koplyčiomis. Tai romantiško ir bizantiško stiliaus derinys. Greta bažnyčios stovi apie 1876 m. pastatyta aukšta mūrinė varpinė. 1898 m. vyskupas Sufraganas Gasparas Felicijonas Cirtautas bažnyčią pakonsekravo Jėzaus Kristaus Dangun žengimo vardu.