Kostel svatého Pavla stojí v pouchlovské části Hradce Králové, obklopený farským hřbitovem. Od roku 1964 je zapsán do seznamu kulturních památek.

Stavba kostela souvisí s vojenským rozvojem města. Roku 1778 byla zbořena původní kostel svatého Pavla na Slezském Předměstí kvůli stavbě hradecké pevnosti. Jako náhrada za něj bylo rozhodnuto vystavět nový chrám na Pouchově. Stavba začala 2. května 1780 pod vedením stavitele Jana Kurze. Dlouho se však nepostahovalo – turecké války výrazně zpomalily práce. Již 29. června 1781 tak děkan a kanovník Moritz Klier vysvětil pouze nedostavěnou část budovy. Rok 1784 přinesl povýšení kostela na farní, o tři roky později sem usedl první farář Jan Dvorský. Roku 1794 k němu přibyly základy kamenné fary se šindelovou střechou.

Vlastní dostavba pokračovala až do 30. let 19. století pod dohledem hostinského Jana Richtera. Věž a západní průčelí byly hotovy roku 1832, samotná dostavba se skončila následující rok a byla vysvěcena třetí neděli adventní. O poměrně krátkou dobu později, 26. května 1840, byly na věž vytaženy první zvony – zvony svatého Petra a Pavla a svatého Antonína.

Architektonicky se jedná o jednolodní stavbu s prvky pozdního baroka. Čtvercový presbytář doplňuje sakristie na jižní straně. Nad presbytářem stojí osmiboký sanktusník s cibulovou kupolí a osvětlením skrz lucernu a makovici. Věž, vzedmutá do výšky 33 metrů, již nese rysy klasicismu a zakončuje ji také cibulová střecha s osmibokými svítilníky a makovicí. Varhany v kostele pocházejí z roku 1901 a postavil je Emanuel Štěpán Petr.

Výzdobu kostela tvoří tři barokní oltáře. Hlavní oltář svatého Pavla je původní barokní stavby. Další dva postranní oltáře jsou rovněž barokního slohu. Zajímavostí je oltář svatého Václava, který město Hradec Králové zakoupilo roku 1786 ze zrušené kaple v bývalém jezuitském semináři. Nový obraz na něj namaloval roku 1868 místní malíř Adolf Russ. Na druhém postranním oltáři se nachází obraz svatého Jana Nepomuckého od malíře Jana Ludvíka Klemense, který jej kostelu sám daroval a později jej roku 1912 opravil J. Štanderou z Hradce Králové. Klemens je také autorem obrazu růžencového oltáře na pravé straně lodi. Nad hlavním oltářem dominuje ještě jeden umělecký prvek – olejomalba s výjevy svatého Pavla na areopágu v Athénách od malíře Josefa Kramolína.

Hřbitov obklopující kostel doplňují dva pomníky: jeden věnovaný padlým z první světové války a druhý připomínající Mistra Jana Husa. Během obou světových válek kostel zažil bolestné ztrátě zvonů. V první válce byly zrekvírovány všechny zvony až na umíráček. Roku 1922 se objevilo elektrické osvětlení díky firmě Antonína Faita. Roku 1925 se zdály vrátily nové zvony, ty však znovu zmizely při rekvizicích během druhé války. Novodobá zvonová výbava pochází z pozdějších let – zvon svatého Pavla byl pořízen roku 1949, později jej roku 2011 doplnil menší zvon Anežky České.

Kostel prošel generální opravou v období 1999–2004, která byla slavnostně završena mší 9. května 2004. Tu celebroval Dominik Duka, v té době královéhradecký biskup.