Heraclea is mentioned in the fifth century in connection with the invasion of eastern Goths in lllyric. In year 479, Theodoric with his Goths comes in lllyric, destroys Stobi and again is in Heraclea. According to the statements, Theodoric left town alone because the bishop from Heraclea has sent him gifts. Later he still robbed and burned the town, and went through the road Via Egnatia to ancient Lychnidos (present Ohrid).
Finally according to a record from, the acts of the Council of Constantinople in 553, for the first time is mentioned Heraclea, with the epithet Pelagoniae. Among the participants of the council mentioned is Bishop of Heraclea Benigus. Name Pelagoniae only was used as evidence that in Heraclea is built residential area on the southern outskirts of Bitola today.
During its thousand years of existence and unfettered development, Heraclea passed, Macedonian, Roman and Byzantine era of the ancient civilization.