Ve většině pramenů se uvádí, že tento kostel pochází z poloviny 14. století, i když někteří autoři soudí, že mohl vzniknout již v tom předchozím, kdy zde existovala již studánka, v níž se podle pověsti osvěžil kníže Václav I. Svatý. Kolem roku 1350 náležel pod bydžovský dekanát a královéhradecký archidiakonát. Roku 1369 bylo odtud odváděno 15 grošů papežského desátku. V roce 1377 prezentoval Heřman ze Staré Vody kněze Matěje na místo zemřelého plebána Alberta, ale ostatní patroni (Unka, plebán v Nechanicích, Čeněk, Racek a Jan z Přestavlk) prezentovali kněze Jana, přičemž kněz Matěj ustoupil a potvrzen byl kněz Jan. Roku 1395 věnoval Prokop Dománkův z Běroniček, jinak z Jikve, zdejšímu kostelu 2 kopy úroku ze Staré Vody. V témže roce Mikeš Kokol ze „Slomon“ (Slemene), sídlící na Přestavlcích, praví, že druhdy ze sbírky osadníků bylo koupeno 7 kop a 6 grošů úroku v Chudeřicích a Staré Vodě na zřízení stálého kaplanství. Jiný zápis však praví, že v roce 1397 Unka, syn Jana, řeč. Šesták, klient z Přestavlk, dal, věnoval a vykázal kostelu 7 kop úroku ze Staré Vody a z Chudeřic a 1 ½ lánu rolí s rybníkem a dvorcem, jak to druhdy Jan, kaplan v Staré Vodě, a jiní kaplani drželi. Za to byl plebán povinen vydržovat 2 vikáře místo dosavadního 1. Jeden vikář měl 3x v týdnu konat služby Boží na tvrzi v Přestavlcích, ale nikoliv o větších svátcích, kdy byl povinen zůstat s plebánem u farního kostela. Z toho vidíme, že došlo ke zrušení kaplanství a místo kaplana byl ustanoven pouhý vikář. Roku 1397 Bransud z Nedabylic daroval kostelu na výročí 1 kopu úroku, kterou koupil od Bernarda z Velkých Běrunic. V roce 1412 si směnil plebán Jan faru s knězem Janem z Dohaliček. V neklidných dobách husitské revoluce a třicetileté války byla zdejší fara opuštěna a spravována z okolí, zejména z Chlumce nad Cidlinou, aby se místní kostel stal nakonec jeho filiálkou. Jinak zde působili kněží podobojí a následně evangelíci.
V 17. století byl chrám předělán do barokní podoby. Tehdy byla upravena zejména loď. Z původního kostela zbyl pouze presbytář s gotickým klenutím. Roku 1714 byl chrám opraven. Není však jasný rozsah těchto prací, nejspíše šlo však pouze o jeho střechu. V roce 1775 byl kostel selskými rebely vykraden. 21. června 1839 uhodil do kostela blesk. V letech 1842-1843 byla opravena střecha. Při této příležitosti byl objeven krov s letopočtem 1612. V roce 1867 byla opravena zvonice, jež získala novou kopuli s křížem. Od 24. ledna 1964 je objekt památkově chráněn (viz
https://www.pamatkovykatalog.cz/kostel-sv-vaclava-13410477). 28. října 1968 byla u zvonice zasazena Lípa svobody, pojmenovaná po armádním generálovi Ludvíku Svobodovi. Roku 1986 byl pořízen nový šindel na opravu střechy, jež byla dokončena o rok později. V letech 2004-2007 byl zrestaurován hlavní oltář a sanováno další dřevěné zařízení. Opravený kostel s novými vchodovými dveřmi byl vysvěcen roku 2008 a v roce 2013 získal novou fasádu a rovněž došlo k opravě sanktusníku.
Jedná se o cihlovou, bezvěžovou jednolodní stavbu na obdélném půdorysu s pravoúhlým presbytářem, k jehož severní straně přiléhá čtvercová sakristie a k jižní straně lodi je přistavěna čtvercová předsíň. Zevně na nároží jsou situovány opěráky. Nad lodí s plochými lizénami a podokapní římsou je nízká sedlová střecha, naopak nad presbytářem se nachází valbová. Uprostřed střechy je oplechovaný osmiboký sanktusník s lucernou, s helmovou střechou a s makovicí. Plochostropá loď má barokní okna, jež jsou segmentově uzavřena. Sakristie je rovněž plochostropá. Presbytář je naopak zaklenut křížovou žebrovou klenbou a triumfální oblouk je hrotitý. Průčelí je završeno barokním obdélným štítem, který je po stranách podepřen konkávně prohnutými křídly a zakončen trojúhelníkem.
Hlavní oltář z roku 1679 je rozvilinový a nese obraz sv. Václava. Spolu se dvojicí bočních oltářů sv. Matěje a Navštívení Panny Marie z roku 1677 měl být zhotoven českotřebovským truhlářem P. Vaňkem a původně vyštafírován J. Bubenským. Obrazy na bočních oltářích jsou však novodobé. Raně barokní kazatelna pochází ze 3. čtvrtiny 17. století. Mezi presbytářem a sakristií byly umístěny kované barokní dveře. Varhany zhotovil v roce 1843 Ignác Welzel z Králík (viz
http://www.varhany.net/cardheader.php?lok=2599).
Trojice zvonů byla od nepaměti zavěšena ve zvláštní zvonici. Dnešní mohutná hranolová dřevěná zvonice s vloženou vzpěradlovou konstrukcí pochází ze 16. století. Roku 1917 z ní byly zrekvírovány 2 zvony, a to z let 1552 a 1543 nebo 1544. Jejich nápisy měly podle obecní kroniky znít takto: „Leta páně 1552 tento zvon jest ulit ku cti a chvále Pana Boha všemohoucího a k záduší Starovodského zkrze Václava Kováře na hradě a za Jana Kvasničky.“ a „Tento zvon jest ulit ku cti a chvále panu Bohu zkrze Václava z Hradci za léta 1544.“ Zbyl pouze velký zvon Václav s textem: „ZYGMVNDA BORZIANOWSKEHO Z BYTYSSKY A NA WOBIEDOWECZCZICH TY CZIASY GEHO MILOSTI RZIMSKEHO CZYSARZE NA CHLVMCZY HEITMANA 1604.“ z let 1604 nebo 1614 (podle publikace „Chlumecko a Novobydžovsko 1“ od Ing. arch. Karla Kuči z roku 1995 ho dal ulít v roce 1604 chlumecký hejtman Zikmund Bořanovský z Bítýšky a na Obědovicích; stejný autor ho však v knize „České, moravské a slezské zvonice“ z roku 2001 datuje do roku 1614; v roce 1775 obdržel nové srdce), pro nějž mohla být podle některých autorů vystavěna právě výše zmíněná zvonice. Roku 2013 proběhla kompletní oprava střechy zvonice, jež byla slavnostně vysvěcena 16. listopadu 2013.