Kada je u drugom stoljeću naše ere ustanovljena nadbiskupija, smatra se da je tada ustanovljena i župa u tadašnjem Skupiju, tj. u današnjem Skopju. Središte Zapadne crkve, koje se u to vrijeme nalazilo u Solunu, premješteno je u Skopje, u takozvani „mali Rim“. Dolaskom Slavena, koji su bili pogani, srušene su mnoge crkve, a poslije, kada Slaveni prihvate kršćansku vjeru, te će crkve ponovno biti sagrađene.
Godine 1054. dolazi do raskola u kršćanstvu, kada se Crkva podijelila na Istočnu i Zapadnu. U Skopju, kao i na cijelom području Makedonije, bilo je vjernika koji su ostali u jedinstvu s Rimom, dok je veći dio bio povezan s Bizantom, odnosno s Carigradom.
Crkva se našla u osobitom položaju kada su Osmanlije osvojile ove krajeve. Njihov odnos prema katoličkim i prema pravoslavnim vjernicima nije bio jednak. Osmanlije su smatrale da je u zapadnom svijetu Papa glavni organizator borbe protiv Osmanskog Carstva. Upravo su zato osobito progonili katolike, počevši od mjesnog biskupa. Rušili su mnoge crkve i samostane, a neke su crkve prenamijenili u džamije, pa je bilo mnogo mučenika – biskupa, svećenika i vjernika laika.
Naposljetku je nadbiskup Pashk Trokshi, uz pomoć austrijske katoličke donacije, uspio sagraditi katedralu u Skopju, koja je 1902. god. posvećena Presvetom Srcu Isusovu. Zajedno s katedralom sagrađena je i biskupska rezidencija te prostorije potrebne za pastoralni rad u župi. Tadašnja se katolička crkva nalazila u današnjem središtu grada (na mjestu gdje je danas Spomen-kuća Majke Terezije), u današnjoj ulici „Makedonija“, koja se u to vrijeme zvala „Široki sokak“. Kada bi sultan došao u pohod Skopju, dočekivali su ga upravo pred katedralom.
Biskupska je rezidencija za vrijeme Drugoga svjetskog rata srušena, a katedrala je oštećena u katastrofalnom potresu 1963. god. O sanaciji srušenih zdanja u Skopju odlučivalo se komisijski: prva je komisija odlučila da se katedrala može obnoviti, dok je druga, iz političkih razloga, odlučila da je treba srušiti. Biskupski je ordinarijat zatim tražio prostor za katedralu i dobio ga između ulice Mitropolit Teodosij Gologanov i ulice Petar Pop Arsov. Tako je 1982. god. sagrađena nova katedrala, a pastoralni je centar dovršen 1983. god. U pastoralnom su centru bili smješteni biskupsko sjemenište i klasična gimnazija za svećeničke kandidate.
U skopskom naselju Bit-pazar postojalo je sirotište za djecu bez roditelja i za siromašne. Sirotište su vodile časne sestre sv. Vinka Paulskog – Kćeri kršćanske ljubavi (Usmiljenke). U sklopu se sirotišta nalazila i kapela posvećena sv. Josipu (koja je u funkciji i danas) te kuća za časne sestre. U potresu 1963. god. srušeni su kapela i sirotište, koji će poslije, uz pomoć humanitarne organizacije iz Beča, ponovno biti sagrađeni, i to u obliku montažnih baraka od kojih je jedna služila kao kapela, a u drugima su živjeli svećenici i časne sestre.
U sklop Skopske župe ulaze gradovi Veles, Tetovo i Gostivar.