Постојећи парохијски Храм Светих апостола Петра и Павла саграђен је 1925.године. Осветио га је Свети свештеномученик Петар Сарајевски. До 1905. године на брду изнад Грахова које се зове „Градина“, постојао је српско-православни манастир којег су на рушевинама римског града подигли свештеници из Далмације. Тај манастир је постојао судећи по свему све дотле док се нису Османлије почеле појављивати у близини Грахова. О свему томе нас извештава учитељ Саво М. Бабић у Босанскохерцеговачком источнику, који нас враћа у историју старог града Граховца најмање 500 година уназад, где се на том истом месту налазила црквина тј. рушевина старе цркве и око ње неколико гробова. Владимир Красић у својој књизи „Устанак у Босни од 1875 до 1878.год.“ наводи и описује да су српски устаници 1877. године под вођством Војводе Голуба Бабића, два дана храбро нападали Турке који су били утврђени на Градини у самом манастиру, у намери да их протерају из Грахова. Трећег дана су Турци преко ноћи побегли запаливши манастир и убивши више од тридесет Граховљана. Наиме чим је почео српски устанак против Османлија у Босни ову је цркву турска резервна војска претворила у касарну. Након Берлинског конгреса тачније 1880. године када су се устаници и народ вратили из Далмације, уз свесрдну помоћ православних хришћана из Грахова су обновили манастир, тако што су на том истом месту подигли црквицу у којој се понекад Божија служба вршила. Као најстарији свештеници који су служили у цркви су из славне породице Билбија, а најпознатији од њих је парох Илија Билбија (1835.-1908.год) који је био свештеник Граховске парохије од времена Невесињске буне (Српског устанка у Босни и Херцеговини ) па скоро све до избијања првог светског рата. Прота Илија се међу првима прикључио устанку у Црним Потоцима и био десна рука вођи устанка Голубу Бабићу. Истицао се храброшћу и истрајношћу у тежњама за ослобођење српског народа на овим просторима. Прота Илија Билбија је сахрањен у гробљанској капели на Мраморју у Грахову коју је подигао још за живота крајем 19. века и у њој сахранио своју младо упокојену супругу Марту. Капела је обновљена након последњих ратних страдања у Грахову од стране свештеничке породице, а захваљујући Оцу Воји Билбији унуку проте Милана обновљено је и постављено ново звоно. Кобне 1905. године гром је погодио цркву на брду Градина изнад Грахова запалио је и срушио. Тада су Граховљани одлучили да направе Цркву у самој вароши, али им аустро-угарска власт то није дозволила. Тек након распада аустроугарске царевине и стварањем Краљевине Срба, Хрвата и Словенаца дата је дозвола за градњу данашње Цркве Светих Апостола Петра и Павла у Грахову. У периоду од 1905. до 1925. год. богослужања су се обављала у цркви брвнари, смештеној испод села Угарци.Када је на Видовдан 28. јуна 1914. год ухапшен Гаврило Принцип, због атентата на престолонаследника Франца Фердинанда, њега су као и многе учеснике у атентату хтели да осуде на смрт, али како је био малолетан и нису имали правну основу за такав чин покушали су да натерају свештеника Милана Билбију тадашњег пароха Црнолушког (ктитора цркве Светог Илије у Црном Лугу) који је крстио Гаврила, да фалсификује његову крштеницу и на тај подмукли начин ипак да га осуде на смрт. Међутим када је прота Милан одлучно одбио тај сраман чин њега су ухапсили припадници аустро-угарске војне милиције ткз. шуцкори и заточили у кули старца Вујадина у Ливну где је трпео страховиту тортуру. У почетку су га мучили најтежим мукама, а онда су га тако изнуреног, скоро на самрти пустили кући. Прота Милан је подлегао ранама и свештеномученичком смрћу умро у својој 46 години. Сахрањен је 30. јула 1916. год. на црнолушком гробљу. Након пуне 102 године од упокојења свештеномученика Милана Билбије извршено је обретење моштију уз благослов Његовог Преосвештенства Епископа бихаћко-петровачког г.Сергија. Дана 15. октобра 2018. год мошти су пренесене у храм Светих Апостола Петра и Павла у Босанско Грахово где су положене и доступне верном народу на поклоњење и целивање. На сличан, свештеномученички начин је пострадао и парох Дамјан (Штрбац) Граховски 1941. год. од стране усташа који су га као једног од виђенијих грађана у Грахову затворили у среском суду и немилосрдно мучили. Након тога су га одвели у логор смрти Јадовно где су га живог одерали и његово беживотно тело у комадима бацили у бездан јаме Јадовно.После другог светског рата вољом тадашњих партијских руководилаца овај Парохијски храм је служио као складиште соли и других грађевинских материјала све до шездесетих година прошлог века када је делимично обновљен,а осветио га је епископ далматински Стефан (Боца). Храм је страдао у пожару 14. априла 1970. године и том приликом је уништен већи део иконостаса. Основано се сумња да је пожар био подметнут. Тадашња комунистичка власт је примењивала сурову бруталност према цркви и свештенству. Осам икона велике вредности је потпуно уништено у овом пожару, а пет је тешко оштећено. Делимична обнова парохијског храма Светих апостола Петра и Павла у Грахову дешавала се у неколико наврата: за време епископа далматинских, Стефана (Боце) и Николаја (Мрђе). Последња обнова започета је за време епископа Хризостома 1993. године, али је због рата и прогона Срба из Босанског Грахова у јесен 1995. године прекинута. Током 2000.-2001. године санирана су оштећења на храму и храм је оспособљен за богослужење. У овом периоду делимично је обновљен ентеријер храма и постављен нови иконостас, дар породице Добријевић. Нова обнова храма је започета 28. септембра 2007. године, а завршена је наредне године. Сами чин освећења и обновљења храма 28. септембра 2008. године извршио је тадашњи Епископ бихаћко-петровачки г. Хризостом.