Kostel byl založen pravděpodobně již v době založení obce po roce 1200. Děkan Rojek v pamětech černčických dokonce tvrdil, že podle stop objevených při opravách v roce 1840 je bohuslavický kostel nejméně o dvěstě až třista let starší než kostel černčický, který byl založen Arnoštem z Talmberka kolem roku 1300. Podle toho by kostel v Bohuslavicích pocházel z roku 1100 nebo dokonce 1000, ovšem v jiné podobě než nyní a to v románském stylu a bez věže.

Přestavěn byl ve stylu gotickém v letech 1359-1373 Sezimou z Dobrušky. Na západní straně byla přidána malá věž s gotickými okny. Na vrcholu věže byla zřízena prkenná zvonice, jakou můžeme vidět na kostele černčickém, nebo krčínském. Jestli v ní však byly někdy zvony, nedá se dnes určit. V této podobě stál kostel až do roku 1687. Tehdy byl zcela přestavěn, byly zřízeny dva hlavní oltáře a provedena vnitřní výzdoba. V roce 1777 byl kostel i věže zevnitř i zvenku obílen a byl zřízen oltář sv. Anny a vystavěna kostnice. K tomu museli obyvatelé vesnice poskytnout, jak poznamenává obecní kniha, pomoc dělnickou a dovoz staviva – dovezeno bylo 287 fůr. Do kostnice byly sneseny z jiného místa kosti zemřelých předků, novější kosti z vykopaných hrobů byly svazovány do bílých prostěradel a ukládány na římsku v kostnici okolo stropu. Varhany z roku 1784 jsou od neznámého výrobce. Další úpravy kostela byly provedeny v roce 1840. V předsíni kostela je umístěna pamětní deska věnovaná padlým v první světové válce. Kostel byl farní od roku 1384, v roce 1626 se stal filiálním kostelem k Novému Městu nad Metují, od roku 1742 dostal lokalistu, který vedl matriky a od roku 1857 se stal farním kostelem a dostal svého faráře.