Већ 911. године помињу се Варјази који су се борили као најамници за Византинце.Око 700 Варјага служило је заједно са Далматинцима као маринци у византијским поморским експедицијама против Критског емирата 902. године, а снага од 629 се вратила на Крит под командом Константина Порфирогенита 949. Јединица од 415 Варјага била је укључена у италијанску експедицију 936. године. такође је забележио да је међу снагама које су се бориле против Арапа у Сирији 955. било варјашких контингената. Током овог периода, варјашки најамници су укључени у велике пратиоце.Године 988.
Василије ИИ је затражио војну помоћ од Владимира И Кијевског да помогне у одбрани свог престола.У складу са уговором који је његов отац склопио након опсаде Доростолона (971), Владимир је послао 6.000 људи Василију.Владимир је искористио прилику да се ослободи својих најнепокорнијих ратника које у сваком случају није могао да плати.Ово је претпостављени датум за формалну, сталну институцију елитне гарде.У замену за ратнике, Владимир је добио Васиљеву сестру, Ану, за брак.Владимир је такође пристао да пређе у
хришћанство и да свој народ приведе у хришћанску веру.Године 989. ови Варјази, предвођени самим Василијем ИИ, искрцали су се у Хрисопољу да поразе побуњеничког генерала Барду Фоку.На бојном пољу, Фока је умро од можданог удара пред очима свог противника;након смрти њиховог вође, Фокине трупе су се окренуле и побегле.Бруталност Варјага је примећена када су прогонили војску која је бежала и „весело их секла на комаде“.Ови људи су чинили језгро Варјашке гарде, која је имала широку службу у јужној Италији у једанаестом веку, док су
Нормани и Лангобарди радили на укидању византијске власти тамо.Године 1018, Василије ИИ је добио захтев од свог катепана Италије, Василија Бојоана, за појачање да угуши лангобардску побуну Мелуса од Барија.Послат је одред Варјашке гарде и у бици код Кане Византинци су остварили одлучујућу победу.