Kiriku arhitekt oli Eliel Saarinen. Kirik ehitati aastatel 1915–1919 ja pühitseti 1. oktoobril / 14. oktoobril 1917. Kirik põles 25. augustil1944, ehitati osaliselt taas üles ja pühitseti 3. juulil1966. Põhjalikult renoveeriti kirik aastatel 2008–2015 ja pühitseti 12. septembril 2015.
Tänavalt tagasiastuva ehitise vasakul poolel paiknev tiibhoone rajati pärast kiriku valmimist ning see ei vasta enam päris täpselt Saarineni esialgsele projektile. Parempoolne tiibehitis jäi aga sõja tõttu sootuks ehitamata.
Kiriku murdkelpkatus on ajastule iseloomulikult. Kiriku põhimahu keskteljel paikneva sihvaka torni allosa kummaski ääres paiknevad hulknurksed kaarjalt väljasopistuvad ärklid, mis aitavad ühtlasi rõhku tõmmata kiriku kesksel kohal paiknevale betoonist valatud ümarkaarjale portaalile. Tornikiiver on püramiidne ja kaetud lakitud vaskplekiga.
Kirikuhoone lõpus paikneb lai apsiid. Transepti ehk ristlöövi välisnurkades ja pikihoone torni kõrvalises läänepoolses osas asuvad abiruumid.
Pauluse kirik on üks väheseid tänapäevani säilinud Eliel Saarineni Soome-perioodil projekteeritud kirikuid. Hoonel on sarnasusi Joensuu ja Lahti raekojahoonetega, mis on samuti Saarineni projekteeritud.
1923. aasta 17. märtsil õnnistati sisse uus altar, mille kujunduse autor oli arhitekt Paul Mielberg. Apsiidi aknad laoti seest kinni, kuid aknad ise säilisid seinte sees. Seetõttu on need ainukesed Pauluse kiriku originaalaknad, mis säilisid ka 25. augusti 1944 põlengus ja hilisemates ümberehitustes.
Altari keskse osa moodustas Amandus Adamsoni (1855–1929) Carraramarmorist 3,5 meetri kõrgune skulptuurigrupp "Tulge minu juurde, kes te vaevatud ja koormatud olete". Skulptuurigrupi ideega olevat tutvunud ja selle ka heaks kiitnud Rooma paavst isiklikult. Realistlikku laadi ja seetõttu ehk kiriku üldise juugendstiiliga mitte nii hästi sobituv skulptuur kujutas Jeesust, kelle parema käe all oli Maarja Magdaleena ja vasaku käe all Jeeriko pime. Säärasel viisil ei oldud igatahes Eestis varem skulptuuri altari juures kasutatud. Altariskulptuuri maksumuseks tuli 1 400 000 marka.[1]See hävis augustis 1944, tänaseks säilinud vaid mõned osad.
Samal aastal paigutati torni ka kaks terasest valmistatud kirikukella, mis olid valatud SaksamaalRuhri linnastus asuvas Bochumis ning mis kaaluvad vastavalt 800 ja 1280 kg. Heino Eller ammutas neist inspiratsiooni oma klaveripala "Kellad" kirjutamiseks. Kellade kogumaksumus oli 350 000 marka.[1]
Kirikuhoone sai keskkütte 1924. aastal. Keskkütte ehitamine läks kokku maksma 700 000 marka.[1]
Vasakpoolne kolmekorruseline tiibhoone ehitati aastatel 1931–1932, parempoolne jäigi ehitamata. 1931. aastal tehti ka esimene raadioülekanne jumalateenistusest.
Kirik põles 25. augustil 1944 ning selle käigus hävis enamik põlevaid osi. Kohe alustati ka varemeteks põlenud hoone taastamist. 1946. aastaks oli kirikul katus peal ja 1947. aastal taastati tiibhoone. Jumalateenistusi peeti sel ajal Aleksandri ja Ülikooli kirikus ning pärast tiibhoone uuesti kasutusele võtmist kiriku tiibhoones. Restaureerimine jäid pooleli, kui 1948. aasta veebruaris arreteeriti koguduse õpetaja Harri Haamer.
Tartu tollane linnavalitsus küll ei pooldanud kiriku taastamist, aga varemeid ka ei lammutatud. Arhitekt Arnold Matteus (1897–1986) kinnitas, et müürid on taastamiskõlblikud ja 23. märtsil1957 lubas Eesti NSV Ministrite Nõukogu jätkata kirikuhoone taastamist.
1959. aastal alustati lagede võlvide ja katusetarinditega tegelemist. Ehitusjärelevalvet teostas ja katuse tööjoonised koostas insener Hugo Oengo. Aasta hiljem võeti käsile ka krohvi- ja maalritöid.
2005. aasta 5. aprilli öösel hävis tules koos sisustuse ja raamatutega kiriku raamatupood. Kogudus hindas põlenguga tekitatud kahju suuruseks 621 443 krooni.[3] Süütaja tabati sama aasta lõpus ning Tartu maakohus mõistis mehe 2006. aastal Tartu Pauluse kiriku süütamise eest neljaks ja pooleks aastaks vangi.[4]
Pärast kirikuhoone lõplikku restaureerimist, mida toetasid ka Tartu linn, Eesti Vabariik ja Euroopa Regionaalarengu Fond, on kiriku peasaalist kujunenud üks Tartu suuremaid kontserdisaale, mis mahutab kuni 300 esinejat ja üle 1000 pealtvaataja.[5] Ehitustööd kirikus algasid 2008. aastal ja lõpetati 2015. aastal.
Tähtajaks valminud kirikusse paigaldati ka kolme manuaali ja 56 registriga orel, mille ehitas firma Paschen Kiel Orgelbau. 23. septembril 2012 pühitseti keldrikorrusel sisse kiriku perimeetrist osaliselt väljapoole rajatud kolumbaarium.
Interjöör
Varia
Kirikus asub kauplus, kus müüakse kristlikku kirjandust ja sümboolikat.
Alates 28. juunist 2002 antakse koostöös Tartu Linna Sotsiaalabi osakonnaga vastavaks tegevuseks remonditud ruumides koguduse keldrikorrusel vältimatut sotsiaalabi sissetulekuta inimestele.