Podle pověsti stávala prý ve Všestarech na místě dnešní fary původně kaple sv. Václava a hřbitov při ní zabíral místo před nynějším kostelem a část dvora dnešní farní budovy a sahal i pod ní až ke silnici. Tuto pověst dokazuje to, že při stavbě staré farní budovy roku 1819 se přišlo na hroby s kostrami a na jiné též v základech současné fary v roce 1847.
Všestarský kostel by měl být poprvé připomenut v roce 1384 (plebánie dokonce k roku 1350) a již tehdy byl farním. Někdy v té době byl zdejším podacím pánem královéhradecký měšťan Zdislav, ale ještě předtím náležel patronát opatovickému klášteru. Ovšem již z roku 1366 pochází zmínka o tom, že Kristina, vdova po královéhradeckém měšťanu Janovi, souhlasila s tím, aby si Matěj, oltářník v Hradci, směnil místo s plebánem Petrem. Po smrti plebána Petra vyvstal spor o to, kdo se stane jeho nástupcem. V roce 1401 prezentovali Vilém starší a Vilém mladší z Duban krňovického plebána Václava, ale královéhradecký měšťan Prokop, řečený Bebl z Břízy, jako patron zastavil prohlášky a prezentoval Hanka. Spor mezi oběma stranami se dostal až do Říma a trval až do roku 1408, kdy Vaník ustoupil a Hanek slíbil, že požádá druhého patrona Viléma Dubánka, sídlícího v Bělečku, aby mu v držení kostela nepřekážel. V roce 1408 Vilém mladší z Duban souhlasil s tím, aby si vyměnili místo Matěj, oltářník sv. Doroty v Hradci, s plebánem Hankem. O rok později došlo k témuž kroku. Tentokrát si směnil své místo Mikoláš z Bílého Újezda s plebánem Matějem. Roku 1429 byl plebán Mikoláš prezentován k oltáři v Hradci, ale „přístup do Hradce byl nemožný“. Opakovala se tak situace minulých let, kdy se patroni kostela nedokázali shodnout, i když již desátým rokem byl držitelem Všestar, resp. jejich části, která náležela Vilému z Duban, a podacího kostelního Jiří z Hradce.
Z jakého materiálu byl původní kostel vybudován, to dnes již nevíme. Podle okolních kostelů můžeme předpokládat, že prvotní objekt byl dřevěný. Ten byl nahrazen roku 1415 zděným kostelem, který byl přestavěn během 1. poloviny 16. století (někdy mezi lety 1551-1559). Z té doby pochází dnešní věž, která stávala v čele původního kostela. Po husitských válkách zde působili faráři podobojí, v roce 1485 kněz Matěj, roku 1556 kněz Jiřík, v roce 1565 kněz Jan (tehdy si stěžoval královéhradecké obecní radě, že všestarské záduší s kostelním zařízením bylo oloupeno o tolik věcí, že se nemá ani při mších s čím posluhovat; město zareagovalo darem stříbrného kalicha s patenou), v letech 1573-1581 farář Jakub Kolínský, roku 1589 kněz Štěpán Březnavský, před rokem 1596 Kliment Nygrin, v roce 1606 Šebestián Háma Benešovský, roku 1612 kněz Štěpán a v letech 1617-1622 Jan Grégory Hradecký. V pobělohorském období byla správa chrámu předána minoritům od kostela sv. Anny v Hradci Králové. Další rozsáhlá úprava kostela proběhla v roce 1794. Během těchto prací objevili řemeslníci kámen s nápisem: „Aedifficatum 1415“, který tak potvrzuje dobu výstavby původního kamenného kostela. Při dokončovacích pracích byl na horní ostění dveří do sakristie umístěn text: „Aedificatum 1415, renovatum 1794“. O 4 roky později se postavila též fara, která byla v roce 1848 zbourána a na jejím místě vybudována stavitelem Františkem Vyleťalem z Heřmanova Městce nová farní budova. V otázce obnovení zdejší fary se materiály rozcházejí, podle dašického faráře P. Josefa Nechvíleho se tak stalo již roku 1774, kdy se měl stát místním prvofarářem bývalý minorita Matěj Ginoška, protože však byl kuklenský klášter zrušen až 24. června 1789, tak zřejmě musí jít o chybu. V zápisech světské kroniky však nalezneme zápis o tom, že tohoto roku byla ves přifařena k Všestarům, takže z toho můžeme uvažovat, že tamní fara musela již existovat. V jiných zdrojích se však nachází až rok 1794. Pokud naopak nahlédneme do jakéhokoliv ročníku přehledu "Catalogus venerabilis cleri saecularis et regularis dioeceseos reginae-hradecensis", tak je zde uváděno zřízení samostatné fary až do roku 1800. Nejspíše tedy šlo zprvu o pouhou minoritskou lokálii a teprve poté se počítá tamní fara jako samostatná.
Později se všestarská farnost rozhodla pozdně gotický kostel zbořit, přičemž k tomu došlo o Velikonocích roku 1842. Na jeho místě byl stavitelem Františkem Kurzem z Hradce Králové vystavěn nový chrám v klasicistním stylu, jenž byl presbytářem orientován k severozápadu (kolmo oproti původnímu půdorysu). Tím se věž, která jako jediná zůstala z původního kostela, ocitla uprostřed jeho boku. K vysvěcení nového svatostánku došlo 17. dubna následujícího roku. Do té doby probíhaly bohoslužby ve Světí. Během prusko-rakouské války sloužil kostel jako lazaret, naopak důstojníci a lékaři byli ubytováni na faře. V té době došlo ke zničení části matrik a rozkradení části inventáře. V roce 1879 byla pořízena čtveřice cínových mešních konviček. 8. října 1896 svolilo místodržitelství, aby byly provedeny opravy na kostele a na faře. K těm došlo příštího roku. 20. května 1908 uhodil blesk do věže, z níž srazil 2,2 m vysoký kamenný kříž, který se pádem rozbil. Nový kříž byl zhotoven a umístěn na věž následujícího roku. V roce 1938 došlo k vloupání do kostela a garáže děkana Msgre. Josefa Kopeckého, kterého nahradil administrátor P. Václav Slavíček, jenž se roku 1940 stal nejen zdejším farářem, ale aktivně se účastnil protinacistického odboje, v jehož rámci vystavoval falešné rodné nebo úmrtní listy, ukrýval pronásledované osoby a přispíval finančně těm, jež byli okupanty nějak postiženi. Podobně se zachoval v roce 1945 jmenovaný administrátor P. Jaroslav Sedlák. Ten se postavil komunistickému režimu, za což byl roku 1950 odsouzen k 10 letům těžkého žaláře. Dlouho se zde neohřáli rovněž jeho nástupci, takže zájem o stav kostela i fary nebyl téměř žádný. Od 24. ledna 1964 je kostel památkově chráněn (viz
https://www.pamatkovykatalog.cz/kostel-nejsvetejsi-trojice-s-ohrazenim-hrbitova-13920350). Teprve tehdy byla obnovena běžná údržba. V roce 1994 byly natřeny okapy a oplechování kostela. Největší opravy však počkaly až na počátek 21. století, kdy došlo k obnově fasády a střešní krytiny. V roce 2002 byl zrestaurován gotický portál na kostelní věži. Roku 2008 byla v sakristii položena nová dlažba a následně byla vymalována. Do budoucna se počítá s výmalbou kostela a opravou varhan (viz
https://farnost-vsestary.webnode.cz/prace-jako-na-kostele/varhany/).
Současný kostel s valbovou střechou je jednolodní obdélná stavba s užším pravoúhle uzavřeným presbytářem a s gotickou věží při jihovýchodní straně. Jeho stěny mají široké nárožní pásové rustiky. Loď je trojosá, s půlkruhovými okny se šambránami, presbytář jednoosý, s půlkruhovým oknem na každé straně. Hlavní průčelí na jihozápadní straně je členěno čtveřicí pilastrů, jež nese římsu a drobnější nízký trojúhelný štít, přičemž nároží má opět širokou pásovou rustiku. Hlavní vchod, k němuž vede pískovcové schodiště, má kamenné ostění a trojúhelný štít v supraportě. Nad ním se navíc nachází velké kruhové okno. Gotická věž z lomového kamene při jihovýchodním boku lodi je hranolová, s opěráky v nárožích a předělena 2 kordonovými římsami. Její vrchol tvoří vysoký štíhlý zděný jehlanec s kytkou ve vrcholu. Ten spolu s kamenným renesančním cimbuřím vznikl až v 17. století. V jihozápadní stěně věže najdeme bohatě zdobený pozdně gotický ostěný portál z doby po roce 1530. Původní dveře jsou pobité plechem a opatřeny trojicí dlouhých závěsů a klepadlem. Uvnitř věže je kamenný šnek vedoucí do zvonice ve 2. patře. Výmalba z roku 1880 je dílem Ludvíka Nejedlého, malíře z Nového Bydžova.
Většina zařízení byla pořízena až po roce 1842, tj. po výstavbě nového svatostánku. Ze starého kostela byl převzat hlavní oltář z roku 1798, který byl zhotoven Janem Engelmanem z Hradce Králové, a postranní oltáře sv. Antonína Paduánského a sv. Františka. Ovšem roku 1882 byla trojice těchto oltářů odstraněna a ve spolupráci s malířem Venzarou vznikly nové v historizujícím slohu (nový hlavní oltář v renesančním slohu s obrazem Nejsvětější Trojice a postranními malbami sv. Metoděje a Cyrila, postranní oltáře sv. Václava a Josefa), a to včetně kazatelny. V téže době byl ze zahraničních darů zřízen k uctění památky padlých v bitvě na Chlumu 3. července 1866 oltář Panny Marie se sochami sv. Anny a sv. Františka, přičemž obraz Panny Marie věnovala Laura Neumanová Strzelecká na památku svého manžela, který padl v bitvě 3. července 1866. Postranní oltář sv. Jana Nepomuckého byl zřízen zejména nákladem faráře P. Václava Koželuha v roce 1868. Varhany zhotovil roku 1845 Josef Jiruška z Hradce Králové, který zároveň přenesl ty původní na Chlum. K jejich opravě došlo v roce 1913 a této práce se zhostil Václav Poláček z Rychnova nad Kněžnou.
Ve zvonici bylo původně zavěšeno 5 zvonů. První z nich, který byl zasvěcen Nejsvětější Trojici, byl vysoký 0,8 m a v průměru měl 1,04 m. Pocházel z roku 1559 a nesl nápis: „LETA PANIE MDLIX TENTO ZWON SLIT GEST KE CZTI A CHWALE TROGICZY SW A K ZADVSSI WSSESTARSKEMV SKRZE WACZLAWA FARARZE W HRADCZY NAD LABEM.“ Druhý o výšce 0,8 m a průměru 0,92 m byl z roku 1750 a nesl nápis: „KE CTI A CHWALE BOZI A S IANV NEPOMVCKYMV W WYSKYM MEGTE IAN ZEIDA 1750.“ Třetí ze zvonů z roku 1798 nesl mnohonásobného zasvěcení, a to Bolestné Panně Marii, sv. Janu Nepomuckému, sv. Janu Křtiteli a Sv. Kříži. Jeho tvůrcem byl Antonín Schneider z Hradce Králové. Čtvrtý zvon o výšce 0,54 m a průměru 0,72 m měl na sobě text: „Slit od Karla Paula Hradec Králové leta Páně 1872.“ Posledním zvonem byl 0,32 m vysoký Umíráček, který měl průměr 0,37 m a byl zasvěcený sv. Barboře. Vedle jejího reliéfu se na něm nacházel nápis: „GOSS MICH IGNATIVS DRACK IN KONIGGRATZ 1779.“ Po vypuknutí 1. světové války byly nejdříve zrekvírovány varhanní píšťaly a roku 1917 4 zvony a byl zde ponechán pouze ten nejstarší. V roce 1930 byly pořízeny 2 nové zvony od brněnské firmy R. Manoušek a spol. z Brna-Husovic. Byly zasvěcené sv. Václavu a Panně Marii (o výšce 72 cm, resp. 61 cm) a k jejich slavnostnímu vysvěcení došlo na 28. září téhož roku. Kvůli nelibého zvuku byl též přelit starý Umíráček, původně zřízený z odkazu farníků roku 1921 u J. Bělohoubka na Pražském Předměstí u Hradce Králové (po přelití měl výšku 0,32 m a vážil 20,5 kg). V dubnu 1942 však byly všechny tři zvony z roku 1930 spolu s tzv. Pozdvihováčkem o výšce 0,24 m a průměru 0,3 m, o němž se mi nepodařilo nic zjistit, zrekvírovány. Z pražského skladu se po osvobození vrátil pouze nejmenší ze zvonů - Pozdvihováček. Dnes tu tedy najdeme pouze dvojici zvonů - Nejsvětější Trojice a Pozdvihováček (viz
https://farnost-vsestary.webnode.cz/historie/kostely/).