Manoma, kad dar 1419 m. Vytautas pastatydino pirmąją bažnyčią Krekenavoje. Rodų dvaro savininkai Aleksiejus ir Stanislovas Vizgirdai-Vizgirdavičiai 1484 m. pastatė medinę bažnyčią ir ją aprūpino. Žemaičių kapitulos arkidiakonui (vyskupo padėjėjui katedroje) Jurgiui Talaičiui 1527 m. dovanota Krekenavos klebonija su visu turtu. 1531 ir 1536 m. funduotos 2 altarijos. Vėliau jos sujungtos į vieną. 1533 m. įsteigta parapinė mokykla.
XVIII a. pirmojoje pusėje bažnyčia sudegė. Arkidiakonas Antanas Valavičius 1736 m. bažnyčią atstatė. Jai 1803 m. pakeisti sienojai. 1811 m. sudegusi altarija neatstatyta. Arkidiakonatui 1832 m. priklausė Krekenavos miestelis ir 6 kaimai. Paskutinis arkidiakonas Benediktas Smigelskis (apie 1784–1879; palaidotas Krekenavoje) paliko istoriografinių darbų, žinių apie lietuvių rašytojus. Rašė lenkų kalba. Dalis rankraščių išversta į lietuvių kalbą.
1886 m. į Krekenavą paskirtas klebonas Pranciškus Žukauskas ėmė rūpintis mūrinės bažnyčios statyba. Kauno gubernatorius 1894 m. leido statyti tik medinę. Sužinojęs, kad degamos plytos bažnyčiai, įsakė plytinę uždaryti, o kleboną P. Žukauską nubausti. Vidaus reikalų ministras gubernatoriaus veiksmus pripažino neteisėtais ir 1896 m. davė leidimą statyti.
Pagal architekto Ustino Golinevičiaus projektą dabartinė mūrinė bažnyčia pastatyta 1896–1902 m. Ją 1907 m. konsekravo vyskupas Gasparas Cirtautas. Nuo senų laikų Krekenava garsėjo Dievo Motinos paveikslu. Tikintieji manė jį esant stebuklingą.
1915–1918 metais Krekenavos klebonijoje gyveno ir kūrė Maironis. 1918 m. įsikūrė pavasarininkų kuopa. Bažnyčioje yra kryžius, kurį pagamino dievdirbys Vincas Svirskis (1835-1916).