Kvůli stavbě pevnosti byl roku 1778 zbořen kostel sv. Pavla na Mýtském podměstí, dnešním Slezském Předměstí, a místo něj byl na Pouchově o 2 roky později založen kostel, který byl zasvěcen témuž patronovi. Návrh kostela vypracoval stavitel Václav Runkas. Dva menší oltáře a dva zvony ze zbouraného kostela byly odvezeny na Nový Hradec Králové, cihly pak byly odváženy na Pouchov a z nich byla stavěna zeď kolem hřbitova. Se samotnou stavbou nového svatostánku se začalo 2. května 1780. Stavěl jej mistr zednický Jan Kurz z Hradce Králové, ale následkem tureckých válek se přestalo stavět, takže toho roku se vystavělo jen presbyterium, loď nebyla dostavěna, „toliko zadní díl, dle uzavření, až by dále dostavěn býti mohl.“ 29. června 1781 tento díl stavby vysvětil děkan a kanovník Moric Klír.
Roku 1784 byl doposud filiální pouchovský kostel povýšen Josefem II. na kostel farní pod patronátem královéhradeckého magistrátu. Kolaturu tvořily: Pouchov, Piletice, Rusek, Slatina, Svinárky a dvory mezi Labem a Orlicí ležící při městě (tj. Slezské Předměstí a Správčice). Později počátkem 19. století byly přifařeny i Věkoše. Počátkem dubna 1786 byl v Hradci Králové zrušen seminář a oltář sv. Václava z jeho kaple koupilo záduší královéhradecké, jež ho přeneslo na Pouchov. Následujícího roku sem byl usazen první farář, kterým byl Jan Dvorský. Též sem byly přifařeny dvory v tu stranu mezi Labem a Orlicí při městě ležící, dále Piletice, Rusek, Slatina a Podhůra. Poněvadž fara nebyla vystavěna, bydlel kněz prozatím ve škole, odkud se později přestěhoval do pronajatého domu. Teprve roku 1794 byla dostavěna přízemní kamenná fara se šindelovou střechou, která dnešní podobu získala až roku 1841. Na vyobrazení kostela z roku 1822, které namaloval Hugo Václav Seykora, můžeme vidět jak vypadal původní kostel. Jižní průčelí bylo rozděleno 2 pilastry na 3 pole. V prostředním byl vchod ukončený poloobloukem a nad ním okno na vrchu onloukovité a dole a po stranách vykrojené. V každém z postranních polí bylo okno poloobloukem sklenuté a v západním průčelí 2 podobná okna, kterým odpovídala 2 okna i ve východním průčelí. V každém rohu jižního průčelí bylo po jednom pilastru. Pilastry nesly vysokou římsu a probíhaly jí. Nad ní se vypínal barokní štít rozdělený 2 pilastry na 3 pole, z nichž v posledním bylo obloukem sklenuté okno. Nad kněžištěm vyčnívala nízká vížka s cibulovitou bání. K západnímu průčelí kostela byla navíc přistavena hřbitovní zeď s výklenky.
Ve stavbě kostela se pokračovalo až v roce 1832, kdy byla přistavěna věž. Následujícího roku byla stavba chrámu dokončena v té rozloze, jakou známe nyní. Stavbu prováděl Jan Richter, hostinský u Modré hvězdy v Hradci Králové a o třetí neděli adventní téhož roku byl kostel vysvěcen. Roku 1838 byla obnovena fresková malba nad hlavním oltářem v presbytáři za 20 zlatých od malíře Františka Rachoty z Miletína. Zvony byly pořízeny až v roce 1839 z odkazu Antonína Blažeje. Větší z nich, sv. Petra a Pavla, vážil 6 q a menší, sv. Antonína, měl hmotnost poloviční. Cena většího činila 1 400 zlatých a menšího 1 200 zlatých. Ulity byly u K. Bellmana v Praze. 26. května 1840 byly oba zvony vytaženy na věž a usazeny tam místním tesařem Matějem Machkem. První varhany sem byly zapůjčeny z Kuklen 27. června 1838. V následujícím roce byly pořízeny za 1 200 zlatých nové varhany, proto byly 21. června 1839 původní varhany odvezeny zpět do Kuklen a na nové se poprvé hrálo 23. listopadu téhož roku. V letech 1850-1860 byla freska nad oltářem zabílena. Visel zde poté obraz od neznámého malíře z roku 1826 a obraz od malíře G. Watzka z roku 1869. V roce 1867 byla zřízena na západní a východní straně barokně skrojená 3 okna, jež nahradila ty původní. 7. prosince 1868 byla vichřicí poškozena střecha kostela, ale hned vzápětí byla opravena. V témže roce byla postavena současná věž. Roku 1877 byl rozšířen starý hřbitov. Roku 1901 byl kostel vymalován Ivanem Jonešem z Hradce Králové. V roce 1902 byla opravena a zrestaurována freska za hlavním oltářem od akademického malíře Martina Matouše z Prahy za 1 000 K. V roce 1922 bylo Antonínem Faitem z Hradce Králové zavedeno do kostela elektrické osvětlení, na něž bylo ve sbírce vybráno 7 000 Kč. V březnu 1923 byla kostelní malba opravena Karlem Jandíkem za 1 683 Kč. Na Květnou neděli 5. dubna 1925 posvětil kanovník Vojtěch Brix nový zvon Maria o hmotnosti 395 kg. 24. dubna téhož roku byly svěceny zvony další: sv. Václav (210 kg), sv. Jan Nepomucký (130 kg), sv. Jos. a sv. Jan Křtitel (40 kg) a sv. Antonín Padovský a sv. František Xaverský (21 kg). Světil je Jan Vrabec, děkan a kanovník z Hradce Králové. Cena těchto nových zvonů činila 24 000 Kč a dodala je firma Buřil a Švagerka z Kuklen. Harmonicky tak ladily ke 108 kg vážícímu zvonu z roku 1921, který měl hlavici od zvonu původního, jenž byl zrekvírován za 1. světové války, přičemž ono období přežil ze všech zvonů jen umíráček z roku 1686. Zvon stál 7 150 Kč a svěcen byl 24. října 1921 kanovníkem kancléřem Františkem Kutnarem z Hradce Králové. V srpnu 1925 byla opravena stavitelem V. Capouškem velká i malá věž kostela a při této příležitosti nalezli tesaři Jan Bouček a Alois Volák v malé báni na velké věži zápis o dostavbě věže z roku 1867. Škody na kostele přinesla vichřice, jež se přehnala nad Hradcem Králové 4. července 1929. 22. ledna 1964 byl objekt zapsán do státního seznamu kulturních památek (viz
https://pamatkovykatalog.cz/kostel-sv-pavla-s-ohrazenim-hrbitova-12605204). V létě 1968 byla prováděna vnější oprava kostela. Jednalo se o novou omítku, přeložení střešní krytiny a nátěr obou věží. Roku 1980 opravil varhany Jaroslav Hubený z Protivína. Nejvíce investičních akcí však bylo do kostela směřováno až po pádu komunistického režimu. Generální oprava kostela trvala zhruba 5 let, byla financována z prostředků farnosti i ze zahraničních darů a zakončena byla mší, kterou 9. května 2004 celebroval královéhradecký biskup Dominik Duka. V dalších letech dochází k celkové opravě jednomanuálových varhan (2008), postavených Emanuelem Štěpánem Petrem v roce 1901, ale dotace přispívají i k mnoha dalším akcím, např. očištění a nátěru veškerých klempířských prvků věže kostela.
Tato jednolodní stavba má krátkou obdélnou loď s téměř čtvercovým presbytářem a s půlkruhovým závěrem se zákristií na jižní straně presbytáře. Stěny lodi jsou hladké nezdobené jen s profilovanou podokapní římsou a kasulovými okny. Střecha je sedlová s půlkuželem nad závěrem kostela. Nad presbytářem je osmiboký sanktusník s cibulovou kupolí, lucernou a makovicí. Původní hlavní oltář malovaný al fresco s obrazem sv. Pavla (G. Watzek, 1869), který nahradil obraz sv. Pavla z roku 1826, a se sochami sv. Václava a sv. Floriana po stranách byl nahrazen plastickým Ukřižováním. Po pravé straně je socha sv. Pavla třímajícího meč. Dva pozdně barokní boční oltáře již nejsou na svém místě. Oltář sv. Václava koupila roku 1786 královéhradecká obec ze zrušené kaple sv. Václava v bývalém jezuitském semináři v Hradci Králové a dala jej do zdejšího kostela. Obraz na něm maloval roku 1868 Adolf Russ z Hradce Králové. Obraz sv. Jana Nepomuckého na druhém oltáři byl namalován a darován J. L. Klemensem z Hradce Králové. Roku 1912 ho opravil Jan Štandera z Hradce Králové. Na zdi je freska pocházející z doby stavby kostela. Zobrazuje sv. Pavla loučícího se s Miletskými. Barokní jsou i postranní oltáře s obrazy sv. Václava a sv. Floriána. V lodi je na pravé straně umístěn triptych Jana Ludvíka Klemense Růžencová Madona mezi sv. Řehořem a sv. Dominikem (1856) a Křížová cesta (1855) od téhož autora, kterou vymaloval podle nákresu Josefa Führicha. Interiér kostela byl v letech 1970-1971 zrekonstruován podle projektu architekta Vladimíra Chvojana. Opraven byl kříž, oltář a tabernákl. Z vnitřní výzdoby je pozoruhodné ještě dřevěné sousoší od řezbáře Soudila a mramorová křtitelnice zhotovená kamenickým mistrem Zdeňkem Ježkem roku 1902. Západní průčelí, které bylo v letech 1832-1833 přestavěno, je členěné čtyřmi plochými pilastry nesoucími nízký trojúhelný štít. Na ose je velký obdélný vstup s mohutnou nadpražní římsou nesenou dvěma volutovými konzolami.
Nad průčelí se vypíná dvoupatrová hranolová věž se stěnami s pásovou rustikou, v patře předělená hlavní římsou. Ve druhém patře věže je ve všech stěnách po jednom půlkruhově zaklenutém okně, nad každým je ciferník věžních hodin. Věž je zakončena oplechovanou cibulovou kopulí s osmibokou lucernou a makovicí. Dříve na věži kostela visely 2 zvony, slité od K. Bellmana v Praze roku 1840 (podle Domečkova a Sálova „Královéhradecka“ v roce 1838, což je pravděpodobnější, protože jejich dárce kanovník Antonín Blažej zemřel téhož roku). Na větším byl reliéf sv. Petra a sv. Pavla a na druhém reliéf sv. Antonína Padovského. Za 1. světové války byly oba zrekvírovány. Stejný osud měla i dvojice zvonů ze sanktusníku, jeden (poledník) ulitý v roce 1799 Antonínem Františkem Schneidrem v Hradci Králové a druhý bez nápisu. Zůstal v něm jen 12 kg těžký umíráček s nápisem: „Obětoval Jan Vojtěch Borecký. Léta 1680.“ Roku 1920 byl pořízen do věže nový 100 kg těžký zvon zasvěcený sv. Pavlu od broumovského zvonaře Oktaviana Wintra a o 5 let později do ní byly opatřeny tři zvony, zasvěcené Panně Marii (395 kg), sv. Václavu (210 kg) a sv. Janu Nepomuckému (130 kg). V roce 1925 byly navíc dány 2 zvony do sanktusníku, a to zasvěcené sv. Josefu a sv. Janu Křtiteli (40 kg) a sv. Antonínu Padovskému a sv. Františku Xaverskému (21 kg). Všechny jmenované zvony byly ulity firmou Buřil a Švagerka v Kuklenách. Po tomto kroku tedy visely ve věži 4 a v sanktusníku 3 zvony. Zvony opět zmizely během německé okupace. V roce 1949 byl do věže pořízen zvon sv. Pavel a 10. listopadu 2011 byl zavěšen nový zvon sv. Anežka Česká. Posvěcen byl ale již před 6 dny. K očištění obou zvonů došlo v létě 2017, a to zásluhou RNDr. Ivany Rybecké z Prahy.