W maju 1941 roku awansował i został głównym kwatermistrzem, tj. pierwszym zastępcą szefa wojsk lądowych. Na tym stanowisku przygotowywał i wprowadzał korekty do planu wojny ze Związkiem Radzieckim, zwanego operacją Barbarossa.
Na ziemiach polskich, krótko przed atakiem III Rzeszy na ZSRR, stacjonował prawdopodobnie w Nowej Dębie. thumb|Friedrich Paulus na południu Związku Radzieckiego w styczniu 1942 roku thumb|Friedrich Paulus (po prawej) i generał Walther von Seydlitz-Kurzbach w Związku Radzieckim w listopadzie 1942 roku Choć Paulus nie miał doświadczenia w dowodzeniu dużą formacją, wkrótce potem feldmarszałek Walter von Reichenau polecił go na stanowisko dowódcy 6 Armii, którym to Paulus nominalnie został w styczniu 1942 roku. Z tą armią Paulus odniósł szereg sukcesów, m.in. odpierając radziecką ofensywę na Charków w 1942 roku. W sierpniu 1942 roku zdecydowano, iż armia Paulusa zostanie skierowana do walk o zdobycie Stalingradu.