I lavori di costruzione furono rapidissimi. Nell'ottobre 1913 fu stipulato il contratto con l'impresa Giuseppe Tarabbo. Al principio del 1914 fu fatto il tracciamento e in marzo iniziarono gli scavi. Nel corso dell'anno la chiesa s'innalzò sino al tetto. Sorsero anche il campanile, mozzo (sarebbe stato completato soltanto nel 1928), e la sagrestia. La nuovissima chiesa di San Paolo fu aperta al culto il 19 settembre 1915, data in cui il vescovo mons. Serafino vi nominò Rettore lo stesso mons. Tarello.
Ma l'inizio dell'attività parrocchiale non fu così immediato, per varie difficoltà, prima di tutto la mancanza di una vera e propria strada di accesso alla chiesa. Venne poi la prima guerra mondiale, che spense fervori e iniziative. Nel frattempo mons. Tarello adattò nella nuova chiesa tanti arredi - fra cui l'organo - provenienti dalla vecchia chiesa demolita, fece chiudere le finestre con vetri e intonacare le pareti interne. La prima sepoltura che utilizzò la famosa strada n. 4 (via Zara), finalmente aperta, fu proprio quella di mons. Tarello, nel novembre del 1927.
Il complesso e suggestivo rito della consacrazione della chiesa di San Paolo si svolse il 26 settembre 1940, preceduto e seguito da giornate di preghiera. Fu una festa solenne e partecipata, culminata nel solenne pontificale del vescovo mons. Carlo Rossi al nuovo altare in marmo costruito grazie alla generosa sottoscrizione delle famiglie del rione.