‍Helsingin kaupunki luovutti tontin kirkkorakennusta varten Vallilan työväenkaupunginosasta vuonna 1915. Keväällä 1928 päätettiin tuhannen hengen kirkon rakentamisesta tontille. Arkkitehtikilpailuun osallistui 51 kilpailijaa. Arkkitehti Bertel Liljeqvistin ehdotus palkittiin ja otettiin kirkon rakennustyön perustaksi. Paavalinkirkon peruskivi laskettiin syksyllä 1929, ja kirkko vihittiin käyttöön maaliskuussa 1931.

Talvisota vaurioitti kirkon pääsisäänkäynnin pilareita ja yhtä seinää. Sodan jäljet ovat näkyvissä edelleen. Kirkon peruskorjaus valmistui syksyllä 2003. Kirkon alkuperäiseen asuun saattaneen remontin suunnitteli arkkitehtitoimisto Slotte & Schütz.

Punatiilisen kirkon pääsisäänkäynnin yläpuolella on kirkon nimikkopyhä apostoli Paavali kädessään perimätiedon mukaiseen kuolintapaansa viittaava miekka. Paavalin mukaan myös Jumalan sana on Hengen miekka.

Ulko-oven kahvassa ovat uskoa, toivoa ja rakkautta kuvaavat risti, ankkuri ja palava sydän.

Urkulehterillä on lause psalmista 100: ”Käykää hänen portteihinsa kiittäen.” Pyhiinvaeltajan tunnusmerkki, uskon salaisuuden vertauskuva simpukka ja Jumalan valtakuntaa kallisarvoisena aarteena kuvaava helmi toistuvat sivupilareiden lampuissa ja alttarikaiteen kuvioinnissa. Samaa symboliikkaa on käyttänyt kirkon uusien kirkkotekstiilien suunnittelija tekstiilitaiteilija Helena Vaari. Uuden alttarin kansi on ikivanhaa kalkkikiveä, jossa näkyy siellä täällä fossiileja.

Kirkon holvin maalaukset ovat kuvataiteilija Antti Salmenlinnan. Kirkon kupolin ja Jumalan Karitsan on maalannut Ilmari Manninen. Runsaasti koristeltu kupoli kuvaa Taivasta. Kärsivä Karitsa kantaa voitonlippua. Kuorin katossa on Jumalan vertauskuva, kullattu aurinko, ja orjantappuroilla kruunatun Kristuksen kasvot. Alttarin yläpuolella on kuvanveistäjä Elias Ilkan tekemä puinen krusifiksi.

Saarnatuolissa ovat evankeliumin julistajien edelläkävijät, taiteilija Gunnar Finnen neljä evankelistaa Matteus, Markus, Luukas ja Johannes. Saarnatuolin katossa pelikaani ruokkii sydänverellään poikasiaan. Se on vanha Kristuksen kärsimyksen ja Jumalan rakkauden vertauskuva.

Taidemaalari Henry Ericssonin suunnittelema art deco -tyylinen ehtoollisvälinesarja oli esillä Barcelonan maailmannäyttelyssä vuonna 1929.

Kirkon pääurut ovat Kangasalan urkutehtaan vuonna 1931 valmistamat. Urkurakentamo Veikko Virtanen on entisöinyt ne alkuperäiseen asuun vuonna 2005. Uruissa on 48 äänikertaa ja kolme sormiota. Urkurakentamo Martti Porthanin vuonna 2004 valmistamat kuoriurut ovat italialaistyyppiset. Niissä on 12 äänikertaa, yksi sormio ja liitejalkio.

Paavalinkirkko on Paavalin seurakunnan käytössä.

Kirkkoon voi tutustua myös virtuaalisesti.

Lisätyn todellisuuden esittelyvihko