Kostel svatého Jindřicha a Kunhuty byl založen v gotickém slohu ve 2. polovině 14. století při založení Nového Města. Vystavěn byl řádem křížovníků s červenou hvězdou, který ho měl ve správě. Kostel byl obklopen hřbitovem, který byl používán zvláště intenzivně při morových ranách.

V letech 1472–1476 byla založena nová zvonice (dnešní Jindřišská věž), která byla určeno pro nové těžké zvony. Při kostele byla také založena svatojindřišská farní škola.

Po Bílé hoře měl být kostel vrácen křížovníkům, ti se ho však v roce 1646 zřekli ve prospěch barnabitů, ti však tuto nabídku nevyužili a císař Ferdinand III. kostel v roce 1649 převedl na obec Nové Města.

Významná přestavba nastala v roce 1879, kdy byl kostel spolu s přilehlou zvonicí nazývanou Jindřišská regotizován pod dohledem architekta Josefa Mockera. Zrušen byl také přilehlý hřbitov (nepohřbívalo se na něm již od roku 1787) a byl proměněn na malý parčík, pozůstatky náhrobních desek byly přilepeny na fasádu chrámu, některé náhrobky jsou umístěné i ve vstupní části uvnitř kostela.

Kostel je zasvěcen králi a císaři Jindřichovi II., který žil v letech 972/3–1024, a jeho ženě Kunhutě. Oba byli kanonizováni několik let po své smrti. Jindřich zřejmě pro svou velkou zbožnost a pro podporu katolické církve, Kunhuta pak za to, že se zřekla pohlavního života. Traduje se pověst, že byla obviněna z nevěry a musela se proto podrobit Božímu soudu. Trestem bylo přejít po rozžhavených radlicích. Pokud by byla nevinna, Bůh by jí před popálením ochránil. A tak se také stalo. Proto je svatá Kunhuta často zobrazována s kostelem a radlicí v ruce.