Kiedy w II wieku naszej ery powstała archidiecezja, przyjmuje się, że powstała wtedy również parafia w ówczesnym Scupi, czyli w dzisiejszym Skopju. Ośrodek Kościoła zachodniego, który w tym czasie znajdował się w Salonikach, został przeniesiony do Skopja, do tak zwanego „małego Rzymu”. Wraz z przyjściem Słowian, którzy byli poganami, zburzono wiele kościołów, a później, gdy Słowianie przyjęli wiarę chrześcijańską, kościoły te zostały odbudowane.
W 1054 roku dochodzi do rozłamu w chrześcijaństwie: Kościół dzieli się na wschodni i zachodni. W Skopju, podobnie jak na całym terytorium Macedonii, byli wierni, którzy pozostali w jedności z Rzymem, podczas gdy większość związana była z Bizancjum, czyli z Konstantynopolem.
Kościół znalazł się w szczególnej sytuacji, gdy te ziemie zdobyli Osmanowie. Ich stosunek do wiernych katolickich i prawosławnych nie był jednakowy. Osmanowie uważali, że w świecie zachodnim to papież jest głównym organizatorem walki przeciw imperium osmańskiemu. Właśnie dlatego szczególnie prześladowali katolików, poczynając od miejscowego biskupa. Burzyli liczne kościoły i klasztory, niektóre świątynie zamieniali na meczety, a wielu biskupów, kapłanów i wiernych świeckich poniosło wtedy śmierć męczeńską.
Ostatecznie arcybiskup Pashk Trokshi, dzięki darowiźnie austriackich katolików, zdołał zbudować w Skopju katedrę, którą w 1902 roku poświęcono Najświętszemu Sercu Jezusa. Wraz z katedrą powstała rezydencja biskupia oraz pomieszczenia potrzebne do pracy duszpasterskiej w parafii. Ówczesny kościół katolicki stał w dzisiejszym centrum miasta (w miejscu, gdzie dziś znajduje się Dom Pamięci Matki Teresy), przy dzisiejszej ulicy „Makedonija”, która w tamtym czasie nosiła nazwę „Širok Sokak”. Kiedy sułtan przyjeżdżał z wizytą do Skopja, witano go właśnie przed katedrą.
Rezydencja biskupia została zburzona podczas drugiej wojny światowej, a katedra ucierpiała w katastrofalnym trzęsieniu ziemi w 1963 roku. O odbudowie zniszczonych budowli w Skopju decydowały komisje: pierwsza orzekła, że katedrę można odbudować, druga natomiast, z powodów politycznych, zdecydowała, że katedrę należy rozebrać. Kuria biskupia szukała następnie miejsca pod katedrę i otrzymała działkę między ulicą Mitropolit Teodosij Gologanov a ulicą Petar Pop Arsov. Tak w 1982 roku zbudowano nową katedrę, a centrum duszpasterskie ukończono w 1983 roku. W centrum duszpasterskim mieściło się seminarium biskupie oraz gimnazjum klasyczne dla kandydatów do kapłaństwa.
W skopijskiej dzielnicy Bit-Pazar istniał sierociniec dla dzieci osieroconych i dla ubogich. Prowadziły go siostry św. Wincentego a Paulo — Siostry Miłosierdzia (szarytki). Przy sierocińcu znajdowała się kaplica pod wezwaniem św. Józefa (czynna także dzisiaj) oraz dom sióstr. Podczas trzęsienia ziemi w 1963 roku kaplica i sierociniec zostały zburzone; później, dzięki pomocy organizacji humanitarnej z Wiednia, odbudowano je w formie baraków montowanych, z których jeden służył za kaplicę, a w pozostałych mieszkali kapłani i siostry.
Do parafii skopijskiej należą także miasta Veles, Tetovo i Gostivar.