The author subjects to a comparative analysis the information provided by the Byzantine writer Anna Comnena and Ordericus Vitalis. The course of the Byzantine-Norman War of 1081–1085 and the fate of Polog and Skopie are studied in detail. It is assumed that the population of the two towns was friendly disposed to the Normans and this helped their advance. The author rejects the understanding approved in historiography that the Normans resorted to violence and plunder in the district of Polog and Skopie. The local Byzantine aristocracy too was loyal to the Normans. The restoration of the Byzantine rule in the autumn of 1083 was accompanied by “civilizing” measures including punishment and rewards: Constantinople recompensed the submissive and penalized the disloyal ones.