V těchto místech se měl údajně nacházet minoritský klášter, který byl vybudován na přelomu 13. a 14. století a zanikl za husitských válek v roce 1421. Po jeho rozboření byl materiál z něj využit na výstavbu městských hradeb.
Na vzniku současného kostela měl největší zásluhu novobydžovský děkan Msgre. Matěj Petromyšl Horský, který předtím působil jako farář v Hněvčevsi. Tehdy totiž dosavadní hřbitov u děkanského kostela přestával stačit a kvůli okolní zástavbě ho nebylo možno nijak rozšířit. Po dohodě s výše zmíněným děkanem se rozhodla městská rada zřídit nový hřbitov a vybudovat na něm vhodný kostel. Zmínka o získání pozemku pro tento kostel pochází ze zápisu ze 7. listopadu 1601 v Bílé knize kropené, kde se píše: „Tehož leta a dne stala se smlouva s Tomášem Libivským, úředníkem na Petrovicích, a purkmistrem i radou zdejší o zahradu za fortnou sloupenskou se 6 jitry luk a ostatním příslušenstvím, jak to vše byl týž Tomáš Libivský před krátkou dobou od paní Elišky Pecingarové z Řehnic, bytem v Hradci Králové, koupil.“ Pecingarovská zahrada se vším příslušenstvím stála obec 325 kop míšeňských, tj. cenu, kterou zaplatil Tomáš Libivský předchozí majitelce, a tudíž na ní ani zbla nevydělal.
Hned poté byly vyhlášeny sbírky na nový hřbitovní chrám, např. roku 1617 odkázal k záduší kostela sv. Trojice 10 kop míšeňských měšťan Mikuláš Bouček. Informace o tom, kdy se začalo s jeho výstavbou, se do dnešních dob nedochovaly. Přesně dokonce neznáme ani dobu jeho dokončení. Můžeme jen odhadovat, že v roce 1620 již byl dokončen, neboť tohoto roku měšťan Severin Brázda odkázal 139 kop míšeňských k záduší děkanského a nového kostela, přičemž žádal, aby byl pohřben v síni nového chrámu. V roce 1645 se dostalo tomuto chrámu dalšího odkazu. Václav starší z Mitrovic a na Humburcích mu ve svém kšaftu odkázal 150 kop míšeňských. Roku 1649 připadly navíc do kostelního záduší pozemky nedaleko chrámu, jež náležely Rejně Krůlové. Tehdy rovněž měšťan Václav Čeněk věnoval 12 kop šindele a zaplatil i veškeré práce na opravě střechy kostela.
Stavba však nebyla nejspíše příliš kvalitní, protože již v roce 1658 byl stav kostela označován za špatný, zejména šlo o jeho klenutí. Na opravu však nebyly myšlenky, protože město bylo postiženo 30. září 1655 velkým požárem, a tudíž nemělo volné finanční prostředky. Stejně tomu bylo i v děkanské pokladně. Oba místní chrámy byly totiž za vpádu saského kurfiřta do Čech oloupeny o většinu kostelního vybavení, jež bylo ze zlata a stříbra. Zabrány však byly také peníze, jež zdejší děkan měl. A tak přestavba kostela byla odsunuta a musela počkat na příznivější doby.
Finanční prostředky se sháněly těžce a různými způsoby, např. v roce 1668 požádal rytíř Adam Měnický z Červené Vsi, aby jeho zemřelá manželka Johana Anežka, rozená Vančurová z Řehnic, mohla být pohřbena v chrámu poblíž oltáře. Za 16 kop míšeňských k záduší sv. Trojice bylo této žádosti vyhověno. Nebývalou aktivitu vyvinul teprve děkan Alexius Květoň z Rosenvaldu, který nechtěl, aby tento chrám spadl někomu na hlavu, a tak začal vyjednávat s městskou radou, jež slíbila nést zčásti náklad na opravu kostela, jež byla provedena v letech 1717-1718 stavitelem Mikulášem Rošym z Mladé Boleslavi (dříve se soudilo, že byl původní kostel dřevěný a nahrazen zděnou novostavbou, pozdější výzkumy tyto teorie nepotvrdily). Za stavitelské práce bylo vydáno 850 zlatých, mladoboleslavský kamenický mistr Josef Strouha obdržel za kamenickou práci a dlažbu 226 zlatých, tesařský mistr Jiří Hák z Mladé Boleslavi dostal za svoji práci zaplaceno 170 zlatých a půl sudu piva, za práci flašnéřskou (klempířskou) bylo vyplaceno 132 zlatých, takže celkový náklad na opravu a přestavbu chrámu vyšel na 1 378 zlatých. Sama oprava byla slavnostně dokončena 13. června 1718, kdy byly na kostel vyzdviženy obě báně.
Po nařízení císaře Josefa II. z 23. srpna 1784 se přestalo pohřbívat u děkanského kostela a všichni nebožtíci tak museli být uloženi k věčnému spánku u sv. Trojice. Protože i zdejší hřbitov však ležel uvnitř města, měl být zrušen i on. V nejbližším okolí však nebylo nalezeno vhodné místo pro pohřbívání, a to zejména kvůli vydatným spodním vodám. Z tohoto důvodu povolil c. k. krajský úřad 3. března 1785 jeho zachování.
Roku 1801 byla prodána veřejnou dražbou zahrada patřící ke kostelu, neboť náklady na její údržbu byly vyšší než příjmy z ní. Za 600 zlatých ji získal měšťan Václav Bartuněk. Již o několik let později byl kostel opět na spadnutí. Opravit ho chtěl již děkan Jan Bendák, jenž však zemřel 19. února 1812. K rekonstrukci chrámu tak došlo až v roce 1838. Tehdy byla šindelová střecha vyměněna za pálené tašky, byla opravena vazba obou věží, jež byly plechem pobity, starý strop byl strhnut a nahrazen novým a nakonec došlo k výmalbě kostela uvnitř i zevnitř. Opravu řídil místní stavitel a architekt Alois Turek.
Za děkana Msgre. Jana Novotného došlo roku 1881 ke zřízení nového hřbitova, protože dosavadní hřbitov u sv. Trojice musel být o rok později uzavřen. O 10 let později zhotovil nový hlavní oltář řezbář Antonín Sucharda z Nové Paky, a to za 48 zlatých. Stěny a stropy byly vymalovány zdejším malířem Ludvíkem Nejedlým a došlo i na přeložení taškové krytiny na kostele a opravě poškozených věžních bání. V roce 1905 došlo ke konečnému zrušení hřbitova, jenž byl následujícího roku proměněn v park. Při té příležitosti byla řada ke kostelu připevněných pomníků z 18. a 19. století stržena a otlučena. Vzácnější z nich byly přemístěny na nový hřbitov, případně vráceny na své místo, a to péčí zdejšího muzejního spolku. K další opravě chrámu Páně došlo v roce 1906. Později mnoho využíván nebyl. Přesto zažil i období, kdy se stal známým i mimo hranice města, zejména roku 1930, kdy se v kostele uskutečnily mše v souvislosti s prvním organizačním kursem bohoslovců z Čech a Moravy pro práci mezi mládeží, jenž se konal od 29. června do 4. července 1930 v Novém Bydžově. Od 15. prosince 2009 patří kostel mezi chráněné kulturní památky ČR (viz
https://pamatkovykatalog.cz/kostel-nejsvetejsi-trojice-13408076). V letech 2010-2011 pak došlo k opravě střechy a klempířských prvků.
Jedná se o jednolodní zděný kostel se sedlovou střechou postavený v hlavní ose východ - západ. Na východní straně je kostel uzavřen čtyřbokým presbytářem, na západě průčelím se dvěma nízkými věžemi. Fasáda je členěna lizénami. V interiéru se při západním průčelí nachází zděná kruchta. Hlavní vstup do kostela se nachází v západním průčelí, boční vstupy jsou situovány v osách severního a jižního průčelí. Další vstup se nachází v severním průčelí presbytáře. Na kruchtu a krov se dostaneme po kamenném šnekovém schodišti v jihozápadní věži, schodiště má samostatný vstup v jižním průčelí. Loď kostela je plochostropá s profilovanou podstropní římsou, presbytář je zaklenut křížovou klenbou svedenou do pilastrů, podkruchtí valeně s trojbokými styčnými výsečemi s hřebínky a kůr je plochostropý. Strop lodi a presbytáře je ozdobena výmalbou od již zmíněného malíře Ludvíka Nejedlého, jíž kraluje výjev sv. Augustina v obdélném zrcadle s konkávními rohy a výjevy Panny Marie v přilehlých nikách. Loď prosvětluje 6 oken v šikmých špaletách se segmentovými záklenky. Trojice stejných oken se nachází v presbytáři, ale okno v severním průčelí bylo zaslepeno a ve vzniklé nice byla umístěna socha sv. Jana Nepomuckého. Ve stěnách v podkruchtí a v presbytáři jsou osazeny náhrobky novobydžovských měšťanů ze 17.-19. století, přičemž nejstarší z roku 1620 náleží Severinu Brázdovi.
Mobiliář je převážně barokní z 18. století, který byl doplněn nebo opraven v tom následujícím století. Jde o portálový hlavní oltář z 1. čtvrtiny 18. století s obrazem Nanebevzetí Panny Marie a sochami českých patronů, jehož altare portatile posvětil 18. září 1719 sám královéhradecký biskup Msgr. Vratislav hrabě z Mitrovic, který do něho vložil ostatky sv. Kláry a sv. Benedikta; rokokové boční oltáře z poloviny 18. století s obrazy sv. Anny a sv. Bartoloměje (kopie kolínského obrazu Petra Brandla, sign. VHP), z nichž nejvýznamnější oltář sv. Anny má altare portatile z téhož roku s ostatky sv. Fruktuosa a sv. Benedikty, různé barokní obrazy z téhož času, epitaf V. Fleischnera se sv. Václavem z roku 1719 a socha sv. Rozálie, jež byla přenesena do předsíně z mariánského sloupu na Masarykově náměstí. Původní varhany vznikly kolem roku 1750 a v roce 1880 byly přestavěny místním varhanářem Janem Severou (viz
http://www.varhany.net/cardheader.php?lok=3742).
Ve věžích byly původně umístěny 3 zvony: první s nápisem: „Zvon tento ulit jest ke cti a chvále boží a blahoslavené Panny Marie r. 1870 v Hradci Králové pro chrám Nejsvětější Trojice boží. V Novém Bydžově nákladem bratrstva sv. růžence.“; druhý s textem: „Chvalte Hospodina na cimbály dobře znějící. Žalm 150. Z vděčnosti za boží požehnání nákladem Jana Jedličky, měšťana v Nov. Bydžově, a téhož manželky Anny, pod správou p. Josefa Kneisla, děkana, byl tento zvon pro chrám Páně Nejsv. Trojice v roku 1855 darován. Ulit v Praze od Karla Bellmanna.“; třetí s nápisem: „Anno 1717; Benedicta sit Sanctissima Trinitas!“ O zdejší farnosti lze najít více zde:
https://farnostnb.webnode.cz.