As the first step in his campaign to expel the Ostrogoths from Italy and regain the Italian peninsula for the Eastern Roman [Byzantine] Empire, the new Byzantine Emperor Justinian from his capital in Constantinople dispatched a mercenary army to invade Sicily in 535.

The invading army, under the leadership of Belisarius, found the Sicilians themselves receptive to the expulsion of the Ostrogoths. Belisarius' force found little resistance as it swept across the island. The only spirited defense encountered from the Ostrogoths came at Palermo [Panormus] in the northwest of the island, and that was swiftly overcome.

The new foreign power was to remain in control of Sicily until the arrival of the Saracens almost 300 years later.