Parohia Catedralei Sfântul Iosif a fost înfiinţată în anul 1895 de către Arhiepiscopul Otto Zardetti. Iniţial, parohia Catedralei a avut un teritoriu foarte mare, aproximativ jumătate din suprafaţa Bucureştiului. După înființarea altor parohii în București, teritoriul acesteia s-a restrâns, reprezentând astăzi zona centrală a capitalei.
Parohia Catedralei nu are casă parohială proprie, preoţii ei locuind în palatul arhiepiscopal.

În anii 1872 şi 1873 episcopul Ignazio Paoli a cumpărat două terenuri în mahalaua Stejarului, (între gară şi palatul regal), cu suprafaţa de 816 stânjeni la preţul de 5685 galbeni. Aceşti bani proveneau din vânzarea unor proprietăţi care aparţinuseră franciscanilor, trecute în patrimoniul Vicariatului Apostolic al Valahiei după retragerea călugărilor din Valahia (1869). Costul terenului, cheltuielile notariale şi onorariul arhitectului au epuizat fondurile iniţiale. Din acest moment, episcopul Paoli a început să bată la uşile binefăcătorilor, din ţară şi străinătate, pentru edificarea operei sale.
Construcţia lăcaşului sacru a început în vara anului 1873, după ce Primăria capitalei a eliberat autorizaţia de construcţie (în 17 iulie). În prealabil, Paoli îl contactase personal pe renumitul arhitect vienez Friederich von Schmidt pentru realizarea proiectului. Ctitorul a optat pentru stilul romanic, caracteristic patriei sale de origine, Italia, combinat cu elemente gotice, specifice marilor catedrale ale Europei creştine. Catedrala era destinată generaţiilor viitoare, ca urmare i-au fost stabilite următoarele dimensiuni: 40 m lungime, 20 m lăţime şi 22 m înălţime.
Lucrările propriu-zise au început cu fundaţia prezbiteriului şi a deambulatoriului, sub supravegherea călugărului arhitect Alfons Zegers, chemat special de la Dublin pentru acest scop. Datorită terenului slab, de umplutură, cheltuielile au depăşit cu mult devizele iniţiale.
În toamna anului 1875 a avut loc ceremonia sfinţirii pietrei de temelie a Catedralei. Amintirea acestui moment solemn este gravată pe o placă de marmură, fixată lângă altarul Maicii Domnului: „Lui Dumnezeu cel mare şi bun, în cinstea Sfântului Iosif, logodnicul sfintei Fecioare Maria, preacinstitul şi preavrednicul domn Ignatius Paoli, episcop romano-catolic de Bucureşti, a binecuvântat şi pus această piatră în ziua de 19 septembrie 1875”.
Criza provocată de intrarea României în Războiul de Independenţă (1877) l-a determinat pe episcopul Paoli să întrerupă lucrările la Catedrală; în anii 1878 şi 1879 el s-a axat pe strângerea de fonduri şi pe procurarea materialelor. Şantierul a fost redeschis în februarie 1880, când s-au început lucrările la corpul central al bisericii, format dintr-o navă principală şi două nave laterale. Paoli i-a încredinţeat şantierul arhitectului Carol Benisch. Tot în acest an a fost comandată şi tâmplăria, la Braşov, meşterului Ioan Pongratz.