Název farnosti a kostela se pojí s rozsáhlou obcí Nová Ves nad Popelkou, která leží na obou břecích říčky Popelky a ukrývá bohaté dějiny až do raného středověku.
Kostel svatého Prokopa v Nové Vsi najdeme asi v polovině této rozsáhlé obce, rozkládající se na obou březích říčky Popelky.
Původně na místě zdejšího zděného barokního kostela stával menší dřevěný kostelík, jehož historie se datuje až do přelomu 12. a 13. století.
Některé prameny však uvádějí datum ještě starší a to že byl založen již kolem roku 1100 sloveskými osadníky - od nich také pochází zasvěcení kostela svatému Prokopovi, jakožto nejvýznamnějšímu světci té doby.
Jisté však je, že původní dřevěný kostel stál v obci na počátku 14. století.
První zmínka o zdejším kostele je totiž z roku 1344, kdy patří pod jičínský děkanát.
Prvním známým duchovním na novoveské faře byl Držislav Franěk z Nové Vsi a nastupuje na místo zemřelého Martina v roce 1359.
Během dalších let je kostel zřejmě několikrát přestavován a získává gotickou podobu, v roce 1402 je u kostela přistavěna kaple.
Po husitských bouřích však již v dokumentech není záznam o službách na zdejší faře a tak lze předpokládat, že kostel byl za bouří významně poničen.
V archivu se také nachází zajímavá zpráva z roku 1514 o ultrakvistickém knězi na novoveské faře.
Ten tu však dle dokumentu "zhoubce zemské přechovává" a tak Mikuláš Trčka z Lípy zasílá na faru ozbrojence, aby "zhoubce" hledali a předvedli.
Kněz však dává faru a kostel zabarikádovat a na ozbrojence házet kamení a střílet.
Kostel i fara jsou však dobyty a oni zhoubci jsou předvedeni před zemský soud do Prahy.
První významnou opravou prochází kostel až v roce 1588 za Elišky z Martinic a Valdštejna.
Třicetiletá válka významně zasáhla do života obyvatel Nové Vsi a došlo i na kostel a faru, která během války zaniká.
Po třicetileté válce je pak v dokumentech záznam o tom, že kostel spadá filiálně pod lomnickou faru, a v kostele je sloužena komendátní, tedy dočasná služba.
Snad jen na krátkou dobu v letech 1662 - 1668 je na novoveském kostele farářem Vojtěch Červenka z Turnova, který ale později odchází do Jičína, kde se stává děkanem.
Do současné barokní podoby je kostel přestaven během čtyř let 1765 - 1769 a v té době je kostelu také přistavěna věž - do té doby je u kostela pouze jednoduchá zvonice.
Ve farní knize však lze nalézt zápis o výstavbě kostela a ten udává datum stavby 1747 a stavbu věže datuje do roku 1749.
O přesném datu novodobé dostavby však svědčí i nápis na oblouku stropu "DIVo LoCI aC boheMIae patrono pIetas ereXerat MDCCLXVIIII" s překlady: "Svatému patronu místa a Čechie zbožnost vyzdvihla 1769".
Za vlády císaře Josefa II. je rušena spousta klášterů a jejich osazenstvo je rozesíláno na nově zřizované císařské fary.
V roce 1787 - 1788 je ke kostelu přistavena nová fara a díky rušení klášterů se na novoveskou faru dostává i její první samostatný farář Leopold Jakobi - bývalý převor nedalekého vrchlabského kláštera a kaplan Michal Čejka z paulánského řádu kláštera v Nové Pace.
Další nové fary se pak kostel dočkal v roce 1891, kdy byla fara shledána jako nevyhovující a postavena nová zděná jednopatrová stavba, která se dochovala až do dnešních dnů (i když ve špatném stavu). Stavělo se dva roky a otevřena byla v roce 1893.
V roce 1895 byly kostelu pořízeny nové varhany, které postavil varhanář Josef Kobrle. Jde o jednomanuálový kuželový nástroj stavěný ve dvou symetrických varhaních skříních, varhany se zachovaly do dneška v původní podobě.
V dalších letech zasáhla do života obce a historie kostela 1. světová válka, kdy bylo rozhodnuto o rekvírování kostelních zvonů. Ty byly na věži před válkou čtyři.
Nejstarším zvonem je "mšesvatník" zasvěcený Panně Marii a ten pochází až ze 14. století - zřejmě z doby kdy nařídil papež Jan XXII. večerní zvonění. Jako jediný, díky své historické hodnotě, přežil rekvírování v obou světových válkách.
Druhým zvonem byl 640 kg vážící mohutný zvon sv. Prokop - ten pocházel z doby přestavby kostela, kterou v roce 1588 nařídila Eliška z Martinic, byl však v roce 1859 přelit a za 1. světové války tudíž rekvírován.
Třetím zvonem byl umíráček z roku 1790 a posledním byl 250 kg vážící "poledňák" z roku 1690 (v době rekvizice popisovaný jako prasklý) - oba bohužel taktéž rekvírované pro zbrojní průmysl.
Měly být z kostela dokonce rekvírovány i varhany na cín, ale díky úplatku byly zachráněny.
V roce 1925 byly díky sbírkám zdejšího faráře p. Kratochvíla pořízeny na kostel tři nové zvony - zhotovila je dílna Richarda Herolda z Chomutova a byly vysvěceny 14. června 1925.
Bohužel o všechny tři zvony zvonice opět přišla za rekvizic během 2. světové války.
Po druhé světové válce zvonům doba moc nepřála a tak se dva nové zvony dostaly na věž až v roce 1991 díky sbírkám které proběhly mezi farníky a obyvateli obce.
Větší zvon, vážící 300 kg je zasvěcený svatému Prokopovi a menší zvon pak svaté Anežce České. Slavnostně vysvěceny byly zvony 2. března 1991 a usazeny na zvonici 9. března téhož roku.
Stály 150.000 Kč a zhotovila je zvonařská dílna Tomášková-Dytrychová s. r. o. z Brodku u Přerova.
Novodobý kostel je vystavěn ve stylu baroka, má jednopatrovou věž se zvonovým patrem, zakončenou typickou barokní cibulí.
Střecha kostela je stanová s výraznou přístavbou kněžiště bez sanktusníku. Na levé straně kostela nalezneme drobnou přístavbu sákristie.
Původně se kolem kostela samozřejmě i pohřbívalo, ale hřbitov v 19. století přestával stačit, neboť se obyvatelstvo obce významně rozrostlo a tak bylo v roce 1867 rozhodnuto o výstavbě nového hřbitova na farní půdě asi 200 metrů severně od kostela.
Kostel je do dnešní doby obklopen vysokou kamennou zdí v obvodu původního hřbitova.
