The town of Skupi evolved from an early Roman legionary barracks on the western slope of the "Zlokucansko kale" (Zlokucani Fortress) hill. It is believed that the V Macedonian and the IV Skits legions were situated there. At its peak, the town covered approximately 45 hectares of area. Its citizens were a mixture of native Paionians and newcomers of Dardanian origin. During the second half of the I century A.D., Skupi and its surroundings were settled by a number of colonists. Those were worn-out soldiers, veterans, majority of them from the VII Claudius's legion. Their ethnic origin was not Roman, they were recruited out of various regions of the Empire: Spain, France, Dalmatia, North Africa, Syria. There are also records of the newcomers from the neighbouring town of Stobi, but also the Hellenized Orientals from the regions of Asia Minor, and from Aegean and Thrace. During their long-lasting military service these soldiers became deeply Romanized, thus obtaining the Roman civic rights. That way a large community of the IUS ITALICUM (Roman civic rights) holders was established. Clearly, that was a crucial factor for granting the town the title of Colonia Flavia Skupi. during the Flavius family period (at the time of Emperor Domitian, 84 - 85 A.D.). During the II century, Skupi was particularly representative in shape, with the monumental theatre as a focal point. During the III century troubles started: taking advantage of the struggles for the imperial throne, first the Sarmatians, and later Goths and Herculites marched into Macedonia. There are records of increased construction activities in the town during the IV century. In that period the most representative building, Basilica 1, was built. It was a public building, a courthouse, located in the southern part of the town. Only the 28 metres long eastern section has been excavated. The section once was a large room with wide apsis on its northern end. Its floor is covered by a mosaic with simple geometrical motifs. The preserved wall ornaments include portions of marble beams, bases, and colons, as well as one Corinthian capital. Its estimated dating is the early IV century. At the end of the IV, or the beginning of V century, one early Christian church was built in the town. However, it seems that it had a short life. During the V century, the town was again devastated by barbarians, this time by Attila's Huns. The basilica was presumably restored at the end of the V century, nevertheless it certainly did not survive the notorious earthquake of 518 A.D. that devastated the town of Skupi.
Procopius of Caesarea, a historian, recorded that in the VI century the Byzantine Emperor Justinian, born in the village of Thaurisius in the country of the European Dardanians, built a town and named it Justiniana Prima. It is highly probable that the place of birth of this great emperor was the fortified Gradiste settlement located near the existing village of Taor in the region of Skopje. On 14 April 535, Justinian promulgated a law on institution of an archbisophric in the newly established town of Justiniana Prima. The following provinces were subordinated to this typically autocephalous church: Mediterranean Dacia, Coastal Dacia, a part of Pannonia Secunda, Mezia Prima, Prevalitania, Dardania, and Macedonia Secunda. It is believed that the possible location of this town and its archbisopric might be Fort Kale in Skopje.
Famous early Christian priests from Skupi were: Bishop Dacius (Council at Nichea, 325 A.D.), Bishop Paregorius (council at Serdica /Sofia/, 343 A.D.), Metropolitan Karos (mentioned in a letter by Pope Leon, 458 A.D.), Metropolitan Jovan (Synod in Skupi, the capital of Dardania, 493 A.D.); Archibishop of Justiniana Prima - Benenat (not present at the V Ecumenic Council in Constantinople, 553 A.D.).