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 men formed the nucleus of the Varangian Guard, which saw extensive service in southern Italy in the eleventh century, as the Normans and Lombards worked to extinguish Byzantine authority there. In 1018, Basil II received a request from his catepan of Italy, Basil Boioannes, for reinforcements to put down the Lombard revolt of Melus of Bari. A detachment of the Varangian Guard was sent and in the Battle of Cannae, the Byzantines achieved a decisive victory.