Armiqtë e rinj në perëndim ishin normanët, të cilët filluan pushtimin e Italisë së Jugut në fillim të shekullit të 11-të. Projekti i Bazilit II për ta rikuperuar Sicilinë nga arabët për pak sa nuk ishte realizuar në 1042 nga i vetmi gjeneral i madh në epokën pas-maqedonase, Gjergj Maniaku, i cili u rithirr nga Konstandini IX dhe u vra si pretendent për fronin. Më pas, normanët bënë avancime graduale në Itali. Të kryesuar nga Robert Giskardi, ata morën gjithçka që i dilte përpara; në prill 1071, Bari, fortesa e fundit bizantine, ra pas një rrethimi tre-vjeçar. Sundimi bizantin në Itali dhe shpresa e ripushtimit të Sicilisë morën fund.