La arquidiócesis de Scupi (o Dardania), capital de la provincia romana de Dardania, está documentada por primera vez en el Concilio de Nicea I en 325, en donde estaba presente el obispo Daco. Se conocen otros tres obispos de Scupi: Paregorio, que participó en el Concilio de Sárdica; Ursilio, que firmó la carta escrita por los obispos de Dardania al emperador León I en 458 tras el asesinato del patriarca alejandrinoProterio; y finalmente Juan, que tuvo un intercambio de cartas con el papa Gelasio I entre 490 y 495. En el siglo V Scupi tenía como sufragáneas a las diócesis de Peć, Pristina, Ulpiana y Diocletiana.
Tras la invasión bárbara de 553, la sede fue suprimida y no se sabe nada de ella hasta 882, cuando ya el área era parte del Primer Imperio búlgaro. Las guerras de Bulgaria en el siglo X provocaron una supresión temporal de la sede, pero cuando los búlgaros se convirtieron al cristianismo en el siglo XI, volvió a ser una sede metropolitana. Desde 1004 Skopie fue parte del Imperio bizantino y fue una diócesis del patriarcado de Constantinopla. Tras ser disputada con los serbios, en 1203 pasó al Segundo Imperio búlgaro, alternado con los bizantinos hasta su captura por el Reino de Serbia en 1282, que a su vez la perdieron a manos del Imperio otomano en 1392, cambiando su nombre a Üsküb. Tras la invasión otomana, las iglesias se convirtieron en mezquitas y el palacio del arzobispo en una residencia de gobierno.
Después de 1340 Skopie solo tuvo obispos titulares católicos hasta 1656,[1] cuando volvió a ser recreada como una sede residencial con el nombre de arquidiócesis de Skopie. En 1689, después de la derrota de los turcos en la Batalla de Kahlenberg, los austriacos asaltaron, tomaron e incendiaron la ciudad dejándola en ruinas. Aunque los austríacos se retiraron ese mismo año, la arquidiócesis finalmente pudo ser restaurada, pero hasta 1860 los arzobispos católicos tenían residencia incierta en las montañas de Macedonia o Albania, debido a la hostilidad de los otomanos.
Para regular el estado de la Iglesia católica, el gobierno de Serbia concluyó un acuerdo oficial (concordato) con el Santa Sede el 24 de junio de 1914. Por el segundo artículo de concordato, se decidió que la diócesis de Skopie sería creada como diócesis regular para todo el territorio nuevamente anexionado (incluyendo Prizren), y se estuvo de acuerdo también en que fuera colocada bajo jurisdicción de la arquidiócesis católica de Belgrado.[2] Debido a la Primera Guerra Mundial, esas provisiones no pudieron ser plenamente implementadas, y sólo después de que 1918 nuevos arreglos fueron hechos. El 29 de octubre de 1924 perdió el rango de arquidiócesis y se convirtió en diócesis inmediatamente sujeta a la Santa Sede.
El 16 de marzo de 1926 en virtud del breve Admonet supremi del papa Pío XI se unieron a la sede algunos territorios del vicariato apostólico de Constantinopla, pertenecientes al antiguo Imperio otomano (Monastir —que es la actual Bitola— y adyacencias), que quedaron dentro del Reino de los Serbios, Croatas y Eslovenos, que desde el 3 de octubre de 1929 pasó a llamarse Reino de Yugoslavia.[3]
Al finalizar la Segunda Guerra Mundial, el área quedó bajo el régimen comunista de Yugoslavia.
El 2 de octubre de 1969, en virtud de la bula Ad Ecclesiam Christi del papa Pablo VI, cedió a la arquidiócesis de Antivari la parte de su territorio que formaba parte de la República Socialista de Montenegro y al mismo tiempo unió el título de Prizren (Prisrianensem) al de Skopie y la diócesis tomó el nombre de la diócesis de Skopie-Prizren. Con la misma bula la diócesis pasó a formar parte de la provincia eclesiástica de la arquidiócesis de Sarajevoad instar et ad tempus.[4]
Con la desintegración de Yugoslavia, el 8 de septiembre de 1991 Macedonia se declaró independiente.
El 24 de mayo de 2000, mediante la bula Apostolicum munus del papa Juan Pablo II, le fue separado el territorio de Kosovo para formar la administración apostólica de Prizren (hoy diócesis de Prizren-Pristina), a la vez que tomó el nombre de diócesis de Skopie.[5]