Gradilište je predano poduzetniku 19. kolovoza 1884. godine, a 25. istog mjeseca obavljen je svečani čin početka radova prije negoli se pristupilo iskopu temelja. Poglavar Zemlje Ivan barun Appel prvi je udario pozlaćenom lopatom tri put a zemlju, a nakon njega to isto je ponovio i nadbiskup, pa ostali prisutni. Mjesec dana kasnije, 23. rujna 1884. povjerenstvo je ustanovilo da su temelji dosta duboko iskopani, naime kod istočnog tornja 5,70 m, kod zapadnog 6,00 m, kod pokrajnjih lađa 7,00 m (zbog nagiba terena), a za stupove između lađa iskopano je do 3 metra dubine. Dana 20. studenog, u 9 sati, uzidan je uz skromnu ceremoniju, u jednom uglu temeljni kamen s urezanim natpisom: A D MDCCCLXXXIV 20. XI. Zidanjem se tokom 1885. godine toliko napredovalo da se u rujnu 1886. moglo svoditi u sve tri lađe. U ožujku 1887. radilo se na zapadnom tornju, a u travnju je počelo žbukanje srednje lađe. Još istoga mjeseca skinute su vanjske skele oko svetišta. Građevinski radovi završeni su 9. studenog 1887. godine u onoj mjeri kako je to bilo ugovoreno s poduzetnikom Schwarzom. Zidovi su, naime, u unutrašnjosti bili samo pobijeljeni, a prozori zatvoreni običnim staklom. Predstojao je, zato, još veliki posao umjetničkog opremanja zgrade, a taj je potrajao pune dvije godine. Vanjska duzina katedrale iznosi 41,90 m, širina 21,30 m, a kod svetišta 24,30 metra. Unutrašnja duzina iznosi 37,65 m, a širina 18,10 metara. Pročelje je flankirano sa dva tornja od po 43,20 metara visine. Krovovi su im u obliku jednostavnih oštrih piramida proširenih pri dnu. Oni flankiraju sporedne lađe prema jugu, dok srednja lađa izbija prema pročelju u svojoj punoj širini. Visoki je zabat pročelja u razini krovišta razveden u pet arkada četiri slijepe i jedna otvorena, u okvirima od pješčara. Pod njim je smješten veliki slijepi luk, a unutar njega je osmerolisna rozeta, izvedena od dva niza gotičkih elemenata. Ispod nje je portal flankiran sa po jednim ranogotičkim stupom u profiliranom dovratniku, a u zabatu je reljef s prikazom sv. Trojstva. Na vrhu portala, dijelom ispred rozete, je kip Srca Isusova, osobni dar poduzetnika Schwarza, izrađen u Beču od margaretskog kamena. Djelo je bečkog kipara A. Hausmanna. Reljef u timpanonu rađen je prema nacrtu A.M. Seitza; modelirao ga je Dragan Morale, kipar zagrebačke katedrale, a u kamen ga je prenio Ivan Novotny. U prizemlju zapadnog tornja smješten je baptisterij, a u istočnom su tornju stepenice za uzlaz na pjevalište i k zvonima. U luku poviše tih vrata zapisan je u kamenu kronogram:

ZA PAPE LEONA XIII, ZA CARA I KRALJA FRANJE JOSIPA I., ZA MINISTRA BENJ. PL. KALLAYA, ZA POGLAVICE ZEMLJE IV. BA­RUNA APPELA, ZA NADBISKUPA Dra STADLERA, BJE OVA CR­KVA SAGRAĐENA PO ARHITEKTU JOS. PL. VANCAŠUU, DNE 14. RUJNA 1889. POSVEĆENA.

U baptisteriju se, nasuprot ulazu, nalazi edikula i baptismalni fons, izvedeni od bijelog mramora. Bit će da su ovi objekti izvedeni po Vancaševu nacrtu. Visoki gotički zabat edikule nose dva stupica od crvenog mramora, a na vrhu je kip Ivana Krstitelja.

Katedrala je izvedena u stilu rane gotike, a Vancaš se, kako izgleda, to poveo za crkvom Notre Dame u Dijonu. Čini se kao da ga je u pogledu vanjskog izgleda lica zidova impresionirala upravo burgundska gotika, tvrda i vrlo škrta arhitektonskim ukrasima. On te činjenice nije nigdje izričito spomenuo, ali tko poznaje prilike u Dijonu i oko Dijona, tome će upasti u oči upravo ove dvije činjenice. Sa izborom svog uzora Vancaš je svjesno pošao na najmarkantniji spomenik rane burgundske gotike. Čini se kao da se potpuno uživio u tu inače župnu crkvu, a ne katedralu, ali dovoljno veliku i reprezentativnu građevinu koja je svojom ljepotom nadmašila obližnje crkve. On je imao pravi osjećaj mjere kada je za skromne sarajevske prilike preinačio neke njezine elemente. Oblik svetišta je zadržao, ali je isturene transepte preobratio a dva dvoetažna aneksa: u sakristiju i riznicu, obje s oratorijem na prvom katu.

Polukružne završetke sporednih lađa u Dijonu, stisnute u ugao između svetišta i transepta, upotrijebio je kao tornjice za stepenice, odmaknute od glavne lađe i prislonjene uz sjeverni zid aneksa. Na mjestu triforija u lađi dijonske crkve on je stavio kružne otvore u koje je umetnuo slike crkvenih Otaca. Rozetu iz transepta prenio je na pročelje. Tim preinakama on je prilagodio građevinu potrebama u sasvim novom ambijentu i sa novom funkcijom. Sarajevska je katedrala zapravo samo donja, parterna polovica dijonske crkve.

On nigdje nije spomenuo ovaj svoj uzor, možda s pravom, jer je u Sarajevu stvorio sasvim novi objekt. Majstori historicizma, uostalom, nikada nisu posebno isticali predložak sa kojega su kopirali svoja djela.

Bilo je veliko umijeće preobličiti usku i vitku francusku crkvu u katedralu suzdržane visine, a da se pri tome ne izgubi sva veličanstvenost rane gotike. Taj omjer je, naime, bliži talijanskoj gotici u konkretnom slučaju crkvi San Francesco u Asizu. Ostat će neodgovoreno pitanje kako mu je pošlo za rukom da u Sarajevu ostvari i tipično burgundski ugođaj jednostavne vanjštine. Naime, tvrdi kamen od kojega su, iznimno u Burgundiji, građene crkve, nije dozvoljavao rasipanje ukrasima, što Vancaš tako uspješno ostvaruje na sarajevskoj katedrali. To nije mogao biti njegov izum, jer on je, ipak, eklektik u epohi historicizma, pa je sve što je stvarao moralo biti negdje viđeno ili naučeno. To je znak da su mu učitelji bili vrsni majstori svojega zanata, ali ih je Vancaš, čini se, pretekao. Ferstelova Votivna crkva u Beču je vrlo hladan i nedorečen objekt; bez obzira što se on tu poveo za francuskom reprezentativnom arhitekturom. Sarajevska katedrala nije neka šablonska građevina, nego sasvim nova i autentična kreacija. On je čist u formi, a realan u izboru materijala. Svojim volumenom i oblicima ona je potpuno prilagođena periferiji historijskog jezgra Sarajeva; ona se ne nameće svojoj okolici. Štoviše, ona čini sa GaziHusrevbegovim hamamom spomeničku oazu na pragu modernog dijela grada.

Tornjevi, ukoliko nisu modelirani prema tornju na prekrižju lađa crkve u Dijonu, onda se čini kao posuđeni sa Tynske crkve u Pragu. Schmidt je izbrisao previsoke krovove na sarajevskim tornjevima, čime ih je još više približio onoj praškoj crkvi.

Oba Vancaševa uzora, Dijon za zgradu, a Prag za tornjeve, čini se da su se u Sarajevu potpuno pomirila i pored toga što su vremenski i prostorno vrlo udaljena. Notre Dame je, naime, dovršena 1240, a Tynska crkva dobila je tornjeve 1458-1463. godine, dakle u vrijeme kada je gotika bila već preživjeli stil. Robustna građa tornjeva Tynske crkve djeluje arhaično, gotovo romanički tvrdo, pa tako ni tornjevi u Sarajevu ne odudaraju od ranogotičkog habita Katedrale u cjelini.

Na bočnim stranama vanjskog lica srednja lađa neznatno nadvisuje sporedne. Vancaš se kod razrade nacrta odlučio za jednostavni krov glavne i sporednih lađa, a svi pod istim nagibom. Time je bazilikalni tip ostao prikraćen za obergaden, a lađa preniska za pravi gotički odnos širine i visine. On umjesto prozora na obergadenu, u razini tavana sporednih lađa ostavlja u unutrašnjosti samo okrugle otvore. Zbog toga je za neposredno osvjetljavanje glavne lađe postavljena rozeta na pročelju i pet prozora u svetištu. No, i prozori u sporednim lađama također daju dosta svjetla unutrašnjosti.

Krov je bio pokriven jednostavnim crijepom tipa dabrova repa. Jedan njegov dio bio je umočen u katran, pa složen tako da su na tornjevima i lađama dobiveni rombični motivi.

Prostorije za sakristiju i riznicu dimenzionirao je preko širine sporednih lađa, čime je u tlocrtu cjelokupne građevine dobiven oblik križa, ali se taj ne odražava u volumenu unutrašnjosti. Oba ova prigratka su dvoetažna, a u prostorije na katu pristupa se izvana zavojitim stepenicama smještenim u posebnim tornjićima. Pri sjevernom završetku sljemena nalazi se tornjić od metala, zvani »sanctus«, koji doseže visinu od 33 metra.

Na ulazu a zapadnu bočnu prostoriju, sakristiju, nalazi se ukrašeni portal, manji, dakako, od onoga na pročelju, ali bogato profiliran. U njegovu je timpanonu prikazana u reljefu Pieta sa dva anđela. Nacrte je izradio A.M. Seitz, modelirao Morak, a u kamenu isklesao Novotny.

Sjeverni završetak zgrade je peterostran i sa pet visokih prozora. Svaki od uglova je pojačan snažnim potpornjacima, kontraforima.

Temelji su do razine unutrašnjeg poda obloženi čvrstim bijelim vapnencem sa Darive; zidovi su izvedeni od vapnenca boje crveno prošaranog okera, porijeklom sa periferije Sarajeva, a vijenci, potpornjaci, uglovi i okviri prozora, dakako i portali, su od pješčara iz okolice Visokog.

Pod je položen wienerberškim keramičkim pločicama u tri tople boje: smeđoj, crvenoj i crnoj, složenim prema Vancaševu nacrtu. Prilikom obnove 1987. godine to su pločice bile uz priličan napor ponovno položene po istom redu nakon što su u pod bile položene instalacije za centralno grijanje. Svod u glavnoj lađi visok je 13,50 m, a u sporednima 8,50 metara.