Već 911. spominju se Varjazi koji su se borili kao plaćenici za Bizantince.Oko 700 Varjaga služilo je zajedno s Dalmatincima kao marinci u bizantskim pomorskim pohodima protiv Kretskog emirata 902., a snaga od 629 vratila se na Kretu pod vodstvom Konstantina Porfirogeneta 949. Jedinica od 415 Varjaga bila je uključena u talijansku ekspediciju 936. To je također je zabilježio da je bilo varjaških kontingenata među snagama koje su se borile protiv Arapa u Siriji 955. Tijekom tog razdoblja, varjaški plaćenici bili su uključeni u Velike ashabe.
Bazilije II. je 988. zatražio vojnu pomoć od Vladimira I. Kijevskog da mu pomogne u obrani prijestolja.U skladu s ugovorom koji je sklopio njegov otac nakon opsade Dorostolona (971.), Vladimir je poslao 6000 ljudi Vasiliju.Vladimir je iskoristio priliku da se riješi svojih najneukrotivijih ratnika, što u svakom slučaju nije mogao platiti.Ovo je pretpostavljeni datum za formalnu, trajnu instituciju elitne garde.U zamjenu za ratnike, Vladimir je za ženu dobio Vasilijevu sestru Anu.Vladimir je također pristao obratiti se na
kršćanstvo i privesti svoj narod kršćanskoj vjeri.Godine 989. ti su se Varjazi, predvođeni samim Bazilijem II., iskrcali u Krizopolju kako bi porazili pobunjeničkog generala Bardu Foku.Na bojnom polju Foka je umro od moždanog udara pred očima svog protivnika;nakon smrti njihovog vođe, Fokine trupe su se okrenule i pobjegle.Brutalnost Varjaga zabilježena je kada su progonili vojsku koja je bježala i "veselo ih sasjekli na komade".Ti su ljudi činili jezgru Varjaške garde, koja je imala široku službu u južnoj Italiji u jedanaestom stoljeću, dok su
Normani i Langobardi radili na gašenju bizantske vlasti tamo.Godine 1018. Bazilije II je primio zahtjev od svog talijanskog katepana, Bazilija Bojoana, za pojačanje kako bi ugušio langobardsku pobunu Mela iz Barija.Poslan je odred varjaške garde iu bitci kod Cannae Bizantinci su ostvarili odlučujuću pobjedu.