Sakralni objekat pravoslavne konfesije je lociran u severoistočnom delu kompleksa Vojne bolnice u neposrednoj blizini Nove (Donje) kapije Podgrađa, odnosno u blizini fortifikacionih bedema. Zapravo, Crkva Sv apostola Pavla sa jednom kasnije izgrađenom kapelom, “drvenim tihovnikom” i parohijskim objektom, nalazi se na samom kraju Ulice Vladimira Nazora sa leve strane.
Ovaj sakralni objekat predstavlja jednu od najmlađih građevina Podgrađa Petrovaradinske tvrđave s obzirom da je sagrađen 1922. godine, odnosno nakon formiranja Kraljevine SHS za potrebe puka vojske Kraljevine Srba, Hrvata i Slovenaca. Crkva je osveštana 14. jula 1926. godine, koji je prema kalendaru Srpske pravoslavne crkve posvećen “Svetim vračevima i čudotvoracima, braći Kozmi i Damjanu”. Tada je ujedno sakralni objekat proširen i dograđen u odnosu na gabarite znatno manje starije kapele koja je izgrađena 1922. godine. Crkvu je osveštao patrijarh Srpske pravoslavne crkve Dimitrije Pavlović (1846 -1930) a iste godine, kralj Aleksandar Karađorđević je tokom svoje posete Petrovaradinu, crkvi poklonio zvono na kojem postoji natpis “Srpskom pravoslavnom narodu Petrovaradina pri hramu Vavedenja Presvete Bogorodice, na dar, Aleksandar Prvi”. Izvorni ikonostas, predstavljao je delo slikara Prve srpske armije, Vase Eškićevića (1867 – 1933).
Ipak, iako je prvi sakralni ortodoksni objekat u Suburbiumu sagrađen tek nakon dezintegracije Habzburške monarhije, odnosno formiranja Kraljevine SHS, sudeći prema zapisima objavljenim u knjizi “Topographische Beschreibung von Peterwardein und seinen Umgebungen” iz 1820. godine, čiji je autor češki apotekar, jedno vreme stanovnik Podgrađa i vlasnik Apoteke “Kod Zlatnog orla”, Franc Šams, u drugoj polovini XVIII veka služba za pravoslavne vernike u Suburbiumu se obavljala u jednom od kazamata lociranom u blizini Beogradske kapije. Sudeći prema sadržaju iste knjige, koja je u srpskom prevodu sa nemačkog publikovana pod nazivom “Istorija Srema i Petrovaradina”, bogosluženje je inicirao i ovu prvu pravoslavnu kapelu u okviru fortifikacionih bedema osveštao Mitropolit karlovački, Pavle Nenadović (1699 – 1768). Bogosluženje, odnosno liturgiju je nedeljom i praznicima, obavljao sveštenik iz Sremske Kamenice a sama kapelica u okviru bedema (kurtini pored Beogradske kapije) je bila u sastavu Vojne bolnice. Kasnije, od sredine XIX veka, umesto stare, takođe u okviru fortifikacionih bedema na suprotnoj strani Podgrađa u neposrednoj blizini danas nepostojeće Novosadske kapije, napravljena je nova kapela za pravoslavne vernike. Ova kapelica je zvanično osvećena i posvećena srpskoj svetiteljki Svetoj Majci Angelini (bivšoj despotici Branković), dok je toranj sa krstom, u kojem je bilo jedno zvono, osvećen 1896. godine. Na osnovu izvora kojima se disponuje, ova Kapela se nalazila u okviru bedema koje su bile orijentisane prema Dunavu. Prvi vojni sveštenik ove crkve-kapele, bio je krušedolski jeromonah German Bošković. U njoj je liturgija vršena sve do postavljanja današnjeg sakralnog objekta 1922. godine.
Kao bogomolja za pukovske potrebe, ovaj sakralni objekat je služio sve do Drugog svetskog rata, da bi nakon njegovog okončanja, usled nacionalizacije crkvene imovine, crkva pretvorena u magacin lekova i sanitarnog materijala Vojne bolnice u Petrovaradinu. Ovu funkciju je imala tokom čitavog perioda postojanja FNRJ i SFRJ, odnosno do dezintegracije komunističkog režima u Jugoslaviji.
Svojoj izvornoj nameni je vraćena 1991. godine, kada je ovaj sakralni objekat od vojske zapravo prešao pod ingirenciju Srpske pravoslavne crkve. Temeljno je rekonstruisan tokom 1992. i 1993. godine, kada je dobio izgled, kakav ima do danas. Odnosno, današnje arhitektonsko rešenje crkve je izvedeno u srpsko-vizantijskom stilu. Idejnim rešenjem rekonstrukcije i izradom projektne dokumentacije, kao i nadzorom na izvođenu radova, rukovodio je arhitekta-konzervator iz Pokrajinskog zavoda za zaštitu spomenika kulture. Ikonopis, odnosno freske u enterijeru objekta, predstavljaju delo beogradskog slikara Dragoljuba Jašovića, dok su ikone na ikonostasu delo slikara Mirka Žeravića.
Nakon završene rekonstrukcije, Crkva je osveštana i od tada do danas se u njoj redovno vrši bogosluženje, dok je sam sakralni objekat poznat pod nazivom Crkva Svetog apostola Pavla u Petrovaradinu. Srpska pravoslavna crkva je zbog povraćaja ovog sakralnog objekta i vraćanja imovine, Vojnomedecinski centar 1998. godine odlikovala Ordenom Sv. Save prvog stepena od strane patrijarha Srpske pravoslavne crkve Pavla.
U arhitektonskom smislu, današnji izgled Crkve Svetog Apostola Pavla, pripada srpsko-vizantijskom stilu. Sakralni objekat karakteriše krstoobrazna osnova sa kvadratnom apsidom, pevničkim prostorima, kao i centralna kupola i zvonik nad zapadnim delom crkve. Spoljašnji deo apside, orijentisan je istočno, prema Ulici Vladimira Nazora i odlikuje se sa dve niše u donjem delu koje su simetrično postavljene i u okviru kojih se nalazi po jedna skulptura: Sv. Apostola Pavla i vojnika. Obe skulpture su izrađene u realističkom stilu i u prirodnoj veličini od bronze i predstavljaju delo vajara Jovana Soldatovića (1920-2005). Unutrašnjost, odnosno enterijer crkve je izveden pod svodovima i bogato je živopisan novim ikonostasom.
Pored crkve, izuzev objekta parohijskog doma, nalaze se i dve manje novije kapele, posvećene Bogorodici. Odnosno, preciznije kapela sagrađena od čvrstog materijala prilikom rekonstrukcije ovog sakralnog objekta početkom devedesetih godina XX veka koja je izrađena u srpsko-vizantijskom stilu, kao i kasnije izgrađen “tihovnik”, napravljen od specifične drvene građe.
Fasada Crkve Sv. Apostola Pavla, kao i manja kapelica uz nju, sagrađene su od cigala i odlikuje ih žuta boja fasade. Park Vojne bolnice koji okružuje Crkvu, kapelu i Tihovnik, odnosno izolovanost mikrolokacije u okviru ambijentalne celine Podgrađa sa brojnim drvećem u neposrednoj okolini, u potpunosti korespondiraju sa sakralnom funkcijom ovog sklopa objekata.
U sklopu dvorišta kompleksa Vojne bolnice, sa suprotne strane, odnosno u okviru jedne niše u bedemu prema Dunavu (u osi objekta nekadašnje Berbernice), nalazi se takođe još jedna manja poluotvorena kapelica sa portalom i zabatom od malterske plastike koji je flanktira u odnosu na ostatak bedema. U okviru ove niše, na svodu, danas postoji prilično oštećena freska Bogorodice sa Hristom u naručju, ispod koje se nalazi česma, kao i mala tabla novijeg datuma na kojoj je ispisana 2002. godina, kao i natpis “VITA EX AQUA / AQUA PRO VITA”. Današni izgled je – u okviru od ranije postojeće niše čija namena do danas nije pouzdano utvrđena, ali se pretpostavlja da je imala sakralni karakter sve do okončanja Drugog svetskog rata – osmislio arhitekta Ilija Protić 2002. godine.
Kompleks objekata i površina Vojne bolnice danas predstavlja jasno izdvojenu prostranu kompleksnu urbanističku i arhitektonsku celinu Suburbiuma, koja zauzima značajan deo severozapadnog dela površine Podgrađa Petrovaradinske tvrđave. Nalazi se unutar severozapadnog bastionog fronta Suburbiuma, oivičen je Bastionom Sv. Jozefa prema Dunavu i prema delu Vaserštata, kao i Bastionom Sv. Terezije orijentisanom prema ostatku fortifikacijskog sistema Donjeg grada Petrovaradinske tvrđave, odnosno prema Vaserštatu (tzv. Vodenom gradu) sa kojim je povezan preko Ispadajuće kapije. Uz bedeme, pruža se sve do Crkve Sv. Pavla, tj. do Nove (Donje) kapije, dok je u okviru unutrašnjosti od ostatka Suburbiuma, oivičen ulicama Vladimira Nazora i Prote Mihaldžića, kao i Trgom vladike Nikolaja. Sastoji se od većeg broja međusobno povezanih i izdvojenih objekata građenih u različitim vremenskim periodima od kraja XVIII do sredine dvadesetih godina XX veka. Arhitektonsku srž kompleksa čini nekoliko međusobno povezanih objekata različite namene, koji su tokom vremena često redefinisani i prekomponovani poput nekadašnjeg objekta Franjevačkog samostana kojem je kasnije pripojena Crkva Sv. Franje a zatim i Zgrada komandanta tvrđave. Kao izolovani objekti unutar kompleksa Vojne bolnice se takođe nalaze: Objekat Velike kasarne, Barutana Terezija (Barutni magazin BIII), Izolovani Paviljon (današnja zgrada Uprave Vojnomedicinskog centra), čitav niz adaptiranih prostorija kazamata između Nove (Donje) i Ispadajuće kapije, objekat „berbernice“, pravoslavna crkva Sv. Pavla sa dve kapele, Ispadajuća kapija, bočne prostorije Nove (Donje) kapije, nekoliko arhitektonskih struktura (bunari, spomenici), kao i sporednih malih objekata novijeg datuma. Izvan same celine kompleksa a u sastavu današnje Vojne bolnice, na Trgu Vladike Nikolaja (br. 4), nalazi se jednospratna zgrada Stare ratne komande.