Talupojaperes kolmeteistkümnenda lapsena sündinud Andrei Vlassov tahtis saada nooruses õigeusu preestriks, kuid bolševike võimupööre ja Vene kodusõda muutis prioriteete – 1919. aastal võeti 18-aastane poiss Punaarmeesse, millega ta sidus edaspidi oma elu. Kodusõja lõpus end hästi näidanud Vlassov jätkas sõjaväelist karjääri. 1929. aastal lõpetas ta kõrgema armee juhtimiskursuse „Võstrel”. 1930. aastal astus kompartei liikmeks. 1935. aastal sai temast Frunze sõjaväeakadeemia kursant.

1938. aasta sügisel lähetati Vlassov Hiina kodusõtta Chiang Kai-sheki sõjaliseks nõunikuks ja 1939. aastal tehti seal temast NSV Liidu sõjalise peanõuniku kohusetäitja. Pärast naasmist 1940. aasta jaanuaris NSV Liitu määrati Vlassov 99. jalaväediviisi ülemaks. Peagi sai sellest diviisist Kiievi sõjaväeringkonna parim ja kogu Punaarmee üks parimaid. Kiievi operatsiooni ajal piirati Vlassovi juhitud 37. armee sisse, selle isikkoosseisust pääsesid vaid vähesed õnneseened, Vlassov nende hulgas.

Novembris 1941 sai Andrei Vlassov uue koha. Talle anti korraldus formeerida ja juhtida 20. armeed, mis osales vastupealetungis sakslaste vastu Moskva lähedal. 20. armee osales Klinsko-Solnetšnogorski pealetungioperatsioonis, kus selle väed lõid puruks vastase 3. ja 4. tankigrupi põhijõud, paiskasid need tagasi Lama jõe – Ruza jõe joonele ja võtsid tagasi mitu asulat, sealhulgas Volokolamski linna Moskva all. Nõukogude ametlik propaganda tõstis Andrei Vlassovi selle eest peetud kangelaste ridadesse. 4. jaanuaril 1942 autasustati Vlassovit nende lahingute eest Punalipu ordeniga ja ülendati kindralleitnandiks.

Jaanuaris 1942 plaanisid Leningradi rinde väed pealetungioperatsiooni, mille eesmärk oli murda Leningradi blokaad. Nõukogude pealetungi esirinnas on 2. löögiarmee, millel õnnestus vastase kaitsest läbi murda ja märkimisväärselt edasi tungida. Punaarmee aga pidi edasi liikuma läbi metsa ja soise maastiku, mis pidurdas nende hoo maha. Asjad läksid hullemaks. 15. märtsil 1942 algas Saksa vastupealetung ja 2. löögiarmeed ähvaras ümberpiiramine. Samas ei peatanud Punaarmee pealetungi ega tõmmanud oma üksuseid tagasi. 2. löögiarmee varustuskoridori pärast peeti ägedaid lahinguid. See lõigati läbi, siis murdsid punaarmeelased uuesti läbi, aga varustuskoridori laiuseks olid napid 1,5 kilomeetrit.