Soon after the province was created, the proconsul Gnaeus Egnatius had a military road built from Dyrrachium (Durrës) on the Adriatic across the mountains to Thessalonica, later extended to Byzantium. In today's North Macedonia it passed Lychnidos (Ohrid) and Heraclea Lyncestis. Milestones survive in the Ohrid area, and the road carried armies, traders, pilgrims and missionaries for more than a thousand years.
Набргу по формирањето на провинцијата, проконзулот Гнеј Егнатиј дал да се изгради воен пат од Дирахиум (Драч) на Јадранот, преку планините, до Солун, кој подоцна бил продолжен до Византион. На територијата на денешна Северна Македонија минувал покрај Лихнид (Охрид) и Хераклеја Линкестиска. Во охридско се зачувани милјоказни камења, а патот повеќе од илјада години служел за војски, трговци, аџии и мисионери.