Parapiją Veliuonoje 1421 m. įsteigė Lietuvos didysis kunigaikštis Vytautas. Jai dovanoti Rūsteikonys. Bažnyčiai 1554 m. dovanoti Girdžių, Gudelių ir Pavidaujo, 1616 m. – Kavolių, Papiškių, 1665 m. – Klangių kaimai. 1579 m. minima parapinė mokykla (veikė ir XVII a.). Apie 1592–1597 m. Veliuonoje nebuvo kunigo. Tada iš bažnyčios buvo atimta beneficinė žemė. 1616 m. padidinta bažnyčia ir parapija.
Albrechtas Stanislovas Radvila 1636–1644 m. pastatė naują mūrinę bažnyčią (konsekravo vyskupas Jurgis Tiškevičius). K. Chšenavičius jai 1686 m. skyrė 10 000 auksinų. 1703 m. minima naujai įsteigta parapinė mokykla (su pertraukomis veikė iki 1863 m.). Kapinėse Zaleskiai 1814 m. pastatė mūrinę koplyčią. Veliuonoje 1815–1831 m. klebonavo Kiprijonas Nezabitauskis-Zabitis (1779–1837), lietuvių poetas, vertėjas. Už 1831 m. sukilimo rėmimą perduotas karo lauko teismui. 1832 m. jis pabėgo iš Lietuvos. Teismo kaltinti ir Veliuonos vikarai J. Lidžius bei V. Rimdeika išteisinti. 1841 m. Veliuonoje gyveno 3 kunigai, parapijai priklausė 50 valakų žemės. Vyskupui Motiejui Valančiui apie 1860 m. pavyko parapijoje įgyvendinti beveik visišką blaivybę. 1864–1870 m. parapijos vikaras buvo Antanas Juška-Juškevičius. Jis čia surinko daug liaudies dainų ir dalį jų 1870 m. išspausdino knygoje „Svotbinė rėdą veliuoniečių lietuvių“. 1885 m. suburtas bažnytinis choras. Jam 30 metų vadovavo vargonininkas Jonas Kumetis. 1887 m. pristatytas priebažnytis, užmūrytos šoninės durys. Bažnyčioje sumontuoti garsaus lietuvių meistro Jono Garalevičiaus pagaminti vargonai. Per Pirmąjį pasaulinį karą bažnyčia apgadinta. Klebonas Z. Polonskis ją suremontavo. Pristatyta medinė bokšto dalis. 1937 m. įrengta parapijos salė.