Православна црква Св. апостола Павла налази се у подграђу Петроварадинске тврђаве у североисточном крилу Војне болнице.На месту данашње цркве се у другој половини 18 века налазила мала војна капела, а дозволу за њу је тражио митрополит Павле Ненадовић. Она је улазила у састав Војне болнице, према Београдској капији, да би се крајем 19 века нашла на супротној страни. 1895. године званично је освећена и посвећена српској светитељки Светој Мајци Ангелини (бившој деспотици Бранковић), док је торањ са крстом, у којем је било једно звоно, освећен 1896. године. Први војни свештеник ове цркве је био крушедолски јеромонах Герман Бошковић.
У оквиру Војне болнице је после уједињења саграђена је 1922. за потребе пука војске Краљевине Срба, Хрвата и Словенаца већа болничка црква.. Први пут је освештена 1926. уочи Светих Врачева 14. јула. Цркву је освештао Патријарх Српске православне цркве Димитрије. Исте године је и краљ Александар Карађорђевић током своје посете Петроварадину, цркви поклонио звоно на којем стоји натпис Српском православном народу Петроварадина при храму Ваведења Пресвете Богородице, на дар, Александар Први. Иконостас је радио сликар Прве српске армије Васа Ешкићевић.
Црква је обављала функцију до Другог светског рата. Након рата национализацијом црквене имовине ова зграда је претворена у магацин лекова Војне болнице у Петроварадину. Тек залагањем припадника Војномедецинског центра у Петроварадину зграда је враћена првобитној намени и обновљена је 1992-93. Војномедецински центар је 1998. одликован орденом св. Саве првог степена од стране Патријарха српске православне цркве Павла.
Залагањем и љубављу протојереја-ставрофора Др Боже Совиља,покреће се у Петроварадину црквени живот. Обновивши храм,обнавља се и духовност у Петроварадину. Прота Божа је пуних 21 годину био парох у овом храму. Овај храм је изњедрио и два која се тренутно граде у Петроварадину. У центру места храм Св.Петке и на Ширинама храм Исповедника Варнаве Беочинског. После одласка у заслужену пензију за старешину храма св.ап.Павла долази протонамесник Благоје Катић.
Првој парохији петроварадинској, при храму светог Апостола Павла у кругу војне болнице, припадају следеће улице :
- ПОДГРАЂЕ ПЕТРОВАРАДИНСКЕ ТВРЂАВЕ – „ГРАДИЋ“
- НАСЕЉЕ „БЛОК 8“ ЗГРАДЕ – улице : ПРЕРАДОВИЋЕВА, ФРУШКОГОРСКОГ ОДРЕДА, ФРАЊЕ ШТЕФАНОВИЋА.
- НАСЕЉЕ „РИБЊАК“( до Телевизије).
- УЛИЦЕ: ДИНКА ШИМУНОВИЋА, ЈОВАНА МОНАСТЕРЛИЈЕ, ТУНИСЛАВА ПАУНОВИЋА, ДРАГУТИНА ШЕНКА,ТОМИСЛАВА МАТАСИЋА, ВИНОГРАДСКА, МАЈУРСКА, КНИНСКА, ТРАНЏАМЕНТСКА, ДУНАВСКЕ ДИВИЗИЈЕ, МАЖУРАНИЋЕВА, КАЧИЋЕВА, , АЛЕКСАНДРА ОСТРОВСКОГ (према Жежељевом мосту).
При храму делује „Православна хришћанска заједница Ваведења Пресвете Богородице“ и мешовити хор“св,Роман Слаткопојац“
У наш храм смо 2015.године пред празник св.Нектарија унели на чување и благослов честице његових светих моштију. Мошти су изложете у кивоту,где благочестиви народ може да дође на поклоњење и молитву.
