Iniciátorem založení samostatné farnosti a kostela na území dnešních Českých Velenic byl Kostelní spolek, který založili v roce 1889 katolíci z osad Česká Cejle, Dolní Velenice a Josefsko (sloučením těchto 3 obcí vzniklo později v roce 1920 město České Velenice ). Stavbu kostela oddalovaly různé překážky, zejména první světová válka. Proto byla jako prozatimní kostel postavena v roce 1915 v Josefsku kaple sv. Rodiny.

16. června 1935 byl posvěcen základní kámen nového kostela. Patronát nad nově založeným kostelem převzal českobudějovický biskup Šimon Bárta, který získal od papeže Pia XI. zvláštní povolení zasvětit kostel tehdy blahoslavené Anežce České (nekanonizovaným světcům se kostely nezasvěcovaly). O stavbu kostela se velmi zasloužil kanovník F. J. Kroiher, děkan v Ledenicích, který také kostel 22. prosince 1935 slavnostně vysvětil.

Kostel je postaven v tehdy moderním slohu;  podle projektu pražského architekta Pilce jej postavil architekt Staněk z Trhových Svinů. Hlavní oltář, kazatelna a křtitelnice jsou z umělého pískovce, kříž na hlavním oltáři je odlitek dle návrhu J.V. Myslbeka, vitráž v okně presbytáře se zobrazením Anežky České je dílem profesora Holečka z Boru u České Lípy. Pro dosažení krásných barev zde umělec použil pravé zlato.

Kolem kostela byl založen anglický park, a v roce 1937 byla při kostele postavena fara.

Za války kostel utrpěl řadu ztrát. Přišel o větší zvon s názvem Sv. Václav a při bombardování města dne 23. března 1945, kdy byla polovina města zničena, byl značně poškozen i kostel. Byla zničena i všechna okna, jen  jediné okno zůstalo nepoškozeno, a to hlavní okno s obrazem blahoslavené Anežky! Kostel poté posloužil k uložení 1500 obětí náletu. Poválečná oprava kostela byla provedena ihned po válce v letech 1945- 1947.

Blahoslavená Anežka Česká byla svatořečena papežem Janem Pavlem II. v Římě 12. listopadu 1989.

V letech následujících po pádu komunistického režimu v listopadu 1989 byly kostel a fara postupně opravovány a modernizovány, většinou ze sbírek a darů. V roce 1998 byl kostel opatřen novým zvonem jménem Sv. Klárra. Zvon posvětil českobudějovický biskup Antonín Liška. 

Oficiální stránky římskokatolické farnosti České Velenice jsou na www.kostelyvitorazska.cz.