Протягом тривалого часу вірні УГКЦ, які проживали в місті Здолбунів, через відсутність святині батьківської для них Церкви, приїжджали на богослужіння в сусіднє місто Рівне. З огляду на таку душпастирську потребу містечка, парох храму св. Миколая (м. Рівне) о. Євген Остапенко вирішує зорганізувати в м. Здолбуневі чергову громаду греко-католиків на теренах Рівненщини. Таким чином, спільними зусиллями душпастиря та місцевого активу вірних 28 вересня 1999 року була зареєстрована парафія святих верховних апостолів Петра і Павла в м. Здолбунів. Живе ядро, молодої громади, складали наступні представники мирянського кола парохії: п. Романа Бучик, п. Любомира Остапчук, п. Любомира Романуха, п. Марія Януль та п. Надія Дедюх.

На початках, Богослужіння відбувалися в приміщенні наданому місцевим заводом "Нестандартного обладнання", однак попри це, також надсилалися клопотання щоб отримати земельну ділянку для побудови храму. Отож на кінець 2002 р. громада отримала земельну ділянку в центрі міста та мобілізувала зусилля, щоб закласти мури для однієї з частин святині.

У грудні 2003 року, для забезпечення душпастирських потреб парохії, було призначено о. Івана Хміля. В цьому ж таки році, об'єднаними стараннями парохіян та жертводавців, розпочалося будівництво храму. Попри складнощі поставленого завдання, вже у березні 2006 року, в одній із частин храму, проходило перше Євхаристійне Богослужіння. 2011 рік для життя спільноти ознаменований величною подією, яка увіковічнила їхні багаторічні старання, оскільки місцевий архиєрей Кир Йосафат (Говера) освятив парохіяльний храм в честь святих апостолів Петра і Павла. З метою забезпечення розвитку харитативного та релігійно-просвітницького аспектів життя парохії, її члени вирішують також розпочати спорудження парафіяльного центру.

На сьогодні парохія налічує близько ста вірних. При громаді діють спільноти: Апостольство молитви, Матері молитви, Жива вервиця та Вівтарна дружина.