Původní kostel na návrší „Byšička“ (též „Na Byšičkách“), jež dnes náleží k obci Brtvi, byl postaven nejspíše již ve 12. století (oficiálně se uznává až století následující), a to v románském slohu. Z něho se zachovala pouze apsida za oltářem. První zmínka o jeho existenci pochází z roku 1267. V témže století měl být přistavěn presbytář. Zda byl již tehdy farním, nevíme. Plebánie tu však existovala již v následujícím století, neboť v roce 1343 Věněk z Byšic prodal Hannovi z Janovic své dědictví a půl vsi Byšic s podacím kostelním. O zdejší plebánii též víme z popisu pražské diecéze z let 1344-1350, podle něhož tehdy zdejší chrám Páně náležel pod jičínský dekanát a královéhradecký archidiakonát. Roku 1360 se stal zdejším farářem kněz Martin, který zastoupil zemřelého plebána Petra. V roce 1369 byly odsud odváděny 4 groše papežského desátku. 23. května 1371 byl prezentován do Byšic místo rezignovavšího plebána Václava kněz Jan z Hněvčevse. 24. listopadu 1406 byl po rezignaci plebána Martina ustanoven k farnímu kostelu v Byšicích kněz Blažek z Nahořan. Během husitských válek zanikla fara, po jejich ukončení byla obnovena, ale již počátkem 16. století patřily Byšičky s podacím a Nový dvůr k Pecce. Po Bílé hoře přestoupil roku 1622 peckovský farář a byšický farní správce Krištof Šteinberger z Altsteinu na katolictví. Svoji manželku si směl u sebe ponechat, ale měl ji od té doby považovat pouze jako hospodyni. Když připadla Pecka kartuziánům, spravovali též Byšičky. V roce 1718 byl kostel přifařen k Nové Vsi (Bělohradu). Roku 1720 byla přistavěna loď a v roce 1850 věž (do té doby stávala na hřbitově dřevěná zvonice). V letech 1851-1880 žil u kostela poslední z českých poustevníků Petr Regulatus, zvaný lidmi též jako Augustýnek (vlastním jménem Augustin Hoření, původně rolník v Brodci u Železného Brodu, zemřel 18. dubna 1880), za jehož života byla u kostela vybudována křížová cesta o 14 kamenných sloupech, jež sloužila svému účelu do roku 1930 a znovuobnovena byla v letech 2001-2002 (oprava sloupků od Františka Žočka, obrazy od Františka Koubka), kdy ji 29. března 2002 vysvětil pomocný královéhradecký biskup Mons. Josef Kajnek. První znovuzřízení kapliček kamenné křížové cesty proběhlo v letech 1903-1904. V roce 1919 byl obnoven oltář Panny Marie. Od 6. února 1964 je objekt památkově chráněn (viz
https://pamatkovykatalog.cz/kostel-sv-petra-a-pavla-12258011). V roce 1988 byla střecha oplechována pozinkovaným plechem. Roku 2009 byla vyhlášením veřejné sbírky zahájena obnova chrámu, např. v letech 2009-2011 bylo provedeno statické zajištění a provedení odvodnění objektu a roku 2016 se dočkala nové fasády severní a jižní strana lodi.
Jedná se o jednolodní orientovanou stavbu s pětibokým presbytářem a věží na západě a půlkruhovou apsidou sakristie s pravoúhlým okénkem na východě. 7,8 m dlouhá, 7,55 m široká a 5,15 m vysoká loď o 3 okenních osách (půlkruhově zakončená okna v jednoduchých širokých šambránách) je obdélná a plochostropá. Při západní straně lodi je vestavěna kruchta na 2 čtyřbokých pilířích. 6,9 m dlouhý a 4,9 m široký presbytář je rovněž plochostropý a jeho východní část je uzavřena apsidou zaklenutou konchou. Triumfální oblouk je hrotitý se skosenou hranou. V presbytáři se nachází sanktuář s rovným štítem a trojlistou kružbou a v jeho volných nárožích jsou situovány 2 diagonální opěráky. Západní hranolovitá věž je jednopatrová s jehlancovou střechou, ve výši hřebene střechy je dělena římsou, nad níž se nacházejí 3 půlkruhově zaklenutá okna v pravoúhlých šambránách a nad nimi v patře 4 velká okna. Vchod uprostřed jižní hlavní zdi je vrouben rovným kamenným ostěním a byl proveden v roce 1718. Střecha kostela je sedlová s valbou.
Výprava kostela je skromná a pochází většinou až z 19. století. Na hlavním oltáři se nachází obraz sv. Petra a Pavla. Dřevěná kazatelna s malbami 4 evangelistů na zlaté půdě podprsníku pochází z počátku 18. století. Kamenná hladká pískovcová křtitelnice v románském slohu má výšku 0,50 m a její mísa má 0,78 m v průměru a pochází nejspíše z počátku 14. století. Varhany byly v polovině 19. století přeneseny z vidochovského kostela Andělů strážných a opraveny roku 1928 firmou Ženatý-Kunt z Lomnice nad Popelkou. Podle legendy jsou v kameni u vchodu otisky kolen sv. Petra modlícího se při zániku obce Byšic o záchranu chrámu. Ke zdejšímu hřbitovu se také váže děj Erbenovy balady Svatební košile.
Ve věži se původně nacházela trojice zvonů, z nichž nejstarší byl ve 2. polovině 19. století ukraden. První zvon měl výšku 0,60 m, průměr 0,67 m a nápis: „WOLEY NEPRZESTAWEY GAKO TRAVBA POWYSS HLASV SWEHO A ZWESTVG LYDV MEMV MRZKOSTI ANNO 1624. IAN FYLIP AVRZEDNIK MATES RYKER, SSTIEPAN NOSAL KOSTELNICI.“; druhý byl vysoký 0,50 m, v průměru měl 0,60 m a byl obdařen textem: „Ke cti svat. apošt. Petra pro filialní chrám Páně na Byšičkách slit od Karla Paula, zvonaře v Královém Hradci 1851.“