Již v roce 911 se uvádí, že Varjagové bojovali jako žoldáci za Byzantince.Asi 700 Varjagů sloužilo spolu s Dalmatiany jako mariňáci v byzantských námořních výpravách proti Krétskému emirátu v roce 902 a síla 629 se vrátila na Krétu pod vedením Konstantina Porfyrogenita v roce 949. Jednotka 415 Varjagů byla zapojena do italské výpravy z roku 936. také zaznamenal, že mezi silami, které bojovaly s Araby v Sýrii v roce 955, byly varjažské kontingenty. Během tohoto období byli varjažští žoldáci zařazeni do Velkých společníků.V roce 988 požádal
Basil II. o vojenskou pomoc od Vladimira I. z Kyjeva, aby pomohl bránit jeho trůn.V souladu se smlouvou, kterou uzavřel jeho otec po obléhání Dorostolonu (971), poslal Vladimir k Basilovi 6 000 mužů.Vladimir využil příležitosti a zbavil se svých nejneposlušnějších válečníků, které v žádném případě nebyl schopen zaplatit.Toto je předpokládané datum formální, trvalé instituce elitní stráže.Výměnou za válečníky dostal Vladimír za manželku Basilovu sestru Annu.Vladimir také souhlasil, že přestoupí na
křesťanství a přivede svůj lid ke křesťanské víře.V roce 989 se tito Varjagové, vedení samotným Basilem II., vylodili v Chrysopolis, aby porazili povstaleckého generála Bardase Phokase.Na bitevním poli Phokas zemřel na mrtvici v plném výhledu na svého protivníka;po smrti svého vůdce se Phokasovy jednotky otočily a utekly.Brutalita Varjagů byla zaznamenána, když pronásledovali prchající armádu a „vesele je rozsekali na kusy“.Tito muži tvořili jádro Varjažské gardy, která v 11. století zažila rozsáhlou službu v jižní Itálii, když se tam
Normani a Langobardi snažili uhasit byzantskou autoritu.V roce 1018 obdržel Basil II žádost od svého katepana v Itálii Basila Boioannese o posílení k potlačení lombardského povstání Meluse z Bari.Byl poslán oddíl varjažské gardy a v bitvě u Cannae dosáhli Byzantinci rozhodujícího vítězství.