Manoma, kad Šeduvoje pirmoji medinė bažnyčia pastatyta ir parapija įkurta 1512 m. Bažnyčiai 1529 m. dovanoti 3 nenaudojami žemės sklypai. 1542 m. fundacija padidinta. Manoma, jog tais metais pastatyta antroji bažnyčia. 1542 m. įsteigta parapinė mokykla.
Upytės vaivada Jeronimas Valavičius 1640–1649 m. pastatė mūrinę bažnyčią. Ją 1649 m. konsekravo vyskupas Jurgis Tiškevičius. 1647 m. įsteigtas Šeduvos dekanatas. Mykolas Mačinskis 1658 m. įsteigė altariją ir ją išlaikė. Šeduvoje 1705–1769 m. veikė jėzuitų misija. XVIII a. greta bažnyčios buvo varpinė (vėliau nugriauta). Bažnyčia 2 kartus degė. Po 1799 m. gaisro dvarininko S. Poniatovskio 1804 m. atstatyta. 1820 m. bažnyčia turėjo 56 valakus žemės su Kleboniškių, Veliakiemių ir Vaižgų kaimais. 1829 m. per žaibo sukeltą gaisrą apgadintas bokštas.
Po 1863 m. Rusijos administracija nusavino pusę parapijos žemių, 1864 m. įsakė nugriauti miestelio aikštėje stovėjusį kryžių. Jo vietoje 1877 m. pastatyta stačiatikių cerkvė (1935 m. nugriauta). XIX a. pabaigoje draudžiamą spaudą platino ir kunigai Stasys Janeliūnas, Pranas Janulaitis, Kazys Marcinkevičius. Klebono Povilo Šalučkos rūpesčiu 1905 m. bažnyčia padidinta: iš šonų pristatytos 2 navos.
1906 m. įsteigtas Šv. Kazimiero draugijos skyrius. Klebono Mamerto Lumbės vadovaujamas „Saulės“ draugijos skyrius steigė lietuviškas mokyklas. Jo įsteigta progimnazija veikė iki 1940 m. Nuo 1926 m. Šeduvoje klebonavusio dekano Mykolo Karoso iniciatyva 1937 m. bažnyčia atnaujinta.
Per Antrąjį pasaulinį karą ji apgriauta. Į Šeduvą 1974 m. paskirtas klebonas kanauninkas Bronius Antanaitis bažnyčią suremontavo ir restauravo. Šeduvoje 1956–1962 m. gyveno ištremtas ir mirė Kaišiadorių vyskupas Teofilius Matulionis.