Rok 1963 na zawsze pozostanie w pamięci mieszkańców Skopja z powodu katastrofalnego trzęsienia ziemi, które nawiedziło miasto. W tym samym trzęsieniu ucierpiała również stara katedra, stojąca w centrum miasta. Dziś w jej miejscu wzniesiono „Dom Pamięci Matki Teresy”. W tamtym czasie katedra była jedynym kościołem katolickim w Skopju. Wspólnota katolicka miasta Skopje poniosła w trzęsieniu ziemi nie tylko straty materialne — jeszcze dotkliwsza była strata duchowa, ponieważ wspólnota została bez godnego miejsca do sprawowania liturgii. Ówczesny biskup, bp Joakim Herbut, zaraz po trzęsieniu ziemi rozpoczął prace nad projektem nowej katedry. Tymczasem na Bit-Pazarze postawiono trzy baraki: jeden służył za kościół, drugi za sale katechetyczne, a trzeci za dom parafialny. Baraki miały być tylko rozwiązaniem tymczasowym, ale ponieważ budowa katedry się przeciągała, całe życie kościelne toczyło się w tym miejscu aż do 1982 roku.
Projekt nowej katedry opracowali dwaj architekci: Slavko Đurić i Blagoja Micevski. Budowa katedry rozpoczęła się w 1975 roku i trwała 7 lat, do 1982. Z ramienia biskupa budowę prowadził ks. prał. Antun Cirimotić.
Myślą przewodnią zewnętrznej bryły katedry jest starotestamentowy obraz namiotu, w którym mieszka Jahwe. Katedrę zbudowano w stylu modernistycznym.
Patrząc na katedrę z zewnątrz, najbardziej rzuca się w oczy konstrukcja dachu, która przecina się na krzyż i tworzy w ten sposób kształt krzyża łacińskiego, a następnie opada ku dołowi, ukazując obraz namiotu.
Centralny żyrandol nad ołtarzem wykonały siostry Świętego Krzyża z Đakova w Chorwacji. Główną myślą przewodnią tej pracy było: Chrystus jako światło, centrum i sens wszystkiego! Siostry starały się przenieść ten obraz w rzeczywistość za pomocą trzech kręgów, z których górny jest największy, a dolny najmniejszy i zarazem najbliższy ołtarza, przez co ukazuje, że Chrystus jest obecny w chlebie i winie na ołtarzu — jest centrum i sensem naszego życia.
Organy są mechaniczne, zbudowane w grudniu 2008 roku; są to pierwsze i jedyne organy w Macedonii. Powstały w Warsztacie Diecezjalnym w Mariborze (Słowenia) i mają następujące parametry: dwa manuały; 26-28 rejestrów; wysokość piszczałek od 15 cm do 5 m; łączna waga 6 ton.
W katedrze znajduje się figura Najświętszego Serca Jezusa, dzieło szkoły tyrolskiej. Figura ta stała w pierwszej katedrze, zniszczonej w trzęsieniu ziemi w 1963 roku, i ma znaczącą historię, ponieważ jako dziewczynka modliła się przed nią święta Matka Teresa. Podczas swoich odwiedzin Skopja, już jako Misjonarka Miłości, po modlitwie przed figurą powiedziała: „Tutaj wszystko się zaczęło”.
Centralna część katedry Najświętszego Serca Jezusa — nawa — oddzielona jest od transeptów dwunastoma aluminiowymi drzwiami w dwóch grupach po sześć, wypełnionymi dwunastoma szklanymi panelami z wizerunkami dwunastu apostołów. Panele wykonano ręcznie w technice szkła topionego (fusing), każdy w naturalnej wielkości. Są przezroczyste, lecz z barwnym tłem i wyrazistą fakturą cieni, z indywidualnymi cechami postaci i podkreślonymi symbolami ich ziemskiej misji.
Są tutaj, duchowo mocno obecni w tej przestrzeni, świadkowie każdych odwiedzin w katedrze, każdej Mszy Świętej i każdego wielkiego święta, gdy bramy katedry otwierają się dla wiernych. Jesteśmy dumni, że byli też świadkami spotkania papieża Franciszka z wiernymi w katedrze podczas jego historycznej wizyty w Skopju 7 maja 2019 roku. Apostołowie są dziełem pracowni „Vitrum” (Art glass) ze Skopja.
Jesienią 2018 roku biskup skopijski i eparcha strumicko-skopijski, bp dr Kiro Stojanov, odnowił katedrę. Wydarzeniem historycznym dla naszego kraju i dla Kościoła w Macedonii była także apostolska wizyta Ojca Świętego papieża Franciszka 7 maja 2019 roku. Przy tej okazji papież Franciszek spotkał się w naszej katedrze z osobami życia konsekrowanego, a na dziedzińcu katedry odbyło się ekumeniczne i międzyreligijne spotkanie z młodzieżą.
