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 v roce 1915 postavena v Josefsku kaple sv. Rodiny jako prozatímní kostel. Bohoslužby zde vykonávali kněží z Gmündu až do roku 1921, kdy byla zřízena v Českých Velenicích samostatná česká duchovní správa.

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 v moderním slohu podle projektu pražského architekta Pilce postavil architekt Staněk z Trhových Svinů. Celkové náklady stavby činily 350 000,- Kč. 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ě apsidy presbytáře se zobrazením Anežky České je dílem profesora Holečka z Boru u České Lípy. K dosažení krásné červené barvy umělec použil pravé zlato. Kolem kostela byl založen anglický park. Fara při kostele byla postavena v roce 1937.

Slibný rozvoj farnosti byl násilně přerušen odtržením Českých Velenic od Československé republiky v říjnu 1938 a následnou okupací. Válečná léta dolehla tvrdě i na zdejší farní kostel. V roce 1942 byl pro válečné účely rekvírován větší z obou zvonů, Sv. Václav. Dne 23. března 1945 byly České Velenice bombardovány a asi polovina města zůstala v troskách. Kostel byl bombardováním též značně poškozen, zejména okenní výplně, dlažba a křížová cesta. Hlavní okno s obrazem blahoslavené Anežky zůstalo nepoškozeno. Kostel posloužil k uložení 1500 obětí náletu. Poválečná oprava kostela byla provedena 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ára, který odlila firma Perner v bavorském Pasově a na jehož úhradě se podíleli českoveleničtí občané, městský úřad a okolní obce. Zvon posvětil českobudějovický biskup Antonín Liška. V roce 2004 byla provedena generální oprava kostelních varhan za přispění fondů Evropské Unie.

V roce 2005 byl z kostela odcizen tepaný měděný poklop křtitelnice.