As early as 911, Varangians are mentioned as fighting as mercenaries for the Byzantines. About 700 Varangians served along with Dalmatians as marines in Byzantine naval expeditions against the Emirate of Crete in 902 and a force of 629 returned to Crete under Constantine Porphyrogenitus in 949. A unit of 415 Varangians was involved in the Italian expedition of 936. It is also recorded that there were Varangian contingents among the forces that fought the Arabs in Syria in 955. During this period, the Varangian mercenaries were included in the Great Companions.

In 988, Basil II requested military assistance from Vladimir I of Kiev to help defend his throne. In compliance with the treaty made by his father after the Siege of Dorostolon (971), Vladimir sent 6,000 men to Basil. Vladimir took the opportunity to rid himself of his most unruly warriors which in any case he was unable to pay. This is the presumptive date for the formal, permanent institution of an elite guard. In exchange for the warriors, Vladimir was given Basil's sister, Anna, in marriage. Vladimir also agreed to convert to Christianity and to bring his people into the Christian faith.

In 989, these Varangians, led by Basil II himself, landed at Chrysopolis to defeat the rebel general Bardas Phokas. On the field of battle, Phokas died of a stroke in full view of his opponent; upon the death of their leader, Phokas' troops turned and fled. The brutality of the Varangians was noted when they pursued the fleeing army and "cheerfully hacked them to pieces".These individuals were the core members of the Varangian Guard, a group that played a role, in Italy during the eleventh century while the Normans and Lombards worked to eliminate Byzantine control in the region. In 1018 Basil II received a plea for assistance from his catepan of Italy, Basil Boioannes to suppress the Lombard uprising led by Melus of Bari. A unit, from the Varangian Guard was dispatched and at the Battle of Cannae the Byzantines achieved a victory.