3 сентября 1940 года Фридрих Паулюс занял пост заместителя начальника Генерального штаба сухопутных сил в должности первого оберквартирмейстера. Ему дали задание создать план вторжения в СССР силами 130–140 дивизий. Целью этого оперативного плана было уничтожение главных сил РККА в приграничных сражениях на западе СССР с последующим выходом на линию Волга — Архангельск, что лишило бы советскую авиацию возможности бомбить рейх.
Паулюс считал, что основной удар следует нанести в Московском направлении. Предварительная линия определялась рубежом Ленинград — Смоленск — Киев, и для этого требовались три группы армий: «Север», «Центр» и «Юг». 29 октября на основе докладной записки Паулюса была издана директива «Ост» по стратегическому сосредоточению и развертыванию сил вермахта. 5 декабря план будущей кампании был подан Гитлеру. Фюрер назвал оперативный план войны с СССР именем германского императора Фридриха Барбароссы, возглавлявшего Третий крестовый поход на Ближний Восток.
После снятия с должности командующего группой армий «Юг» фельдмаршала фон Рундштедта, место которого занял Рейхенау, Гитлер сделал Паулюсу предложение принять командование 6-й полевой армией. 20 января 1942 года Фридрих Паулюс прибыл в Полтаву. В это время группа армий «Юг» вела упорные бои в районе Изюма, где войска Тимошенко пробивали немецкие позиции на стыке 6-й и 17-й армий. 57-я и 6-я ударные советские армии громили боевые порядки вермахта, и передовые отряды почти достигли Днепра в районе Днепропетровска. Но уже в конце февраля наступление Красной армии выдохлось, и прорыв был локализован. Остался выступ в 100 километров глубиной и 80 километров шириной, для ликвидации которого Фридриху Паулюсу пришлось ввести четыре немецких и один румынский корпус.
Весной 1942 года линия фронта проходила в 500 километрах к западу от Сталинграда. Командование, разрабатывая план летней кампании, первоначально собиралось на южном участке фронта провести операцию местного значения восточнее излучины Днепра, чтобы обезопасить марганцевые рудники в Никополе. Однако фюрер упорствовал, и в апреле появился план с выходом к Волге, штурмом Сталинграда и блокадой Кавказа.
Перед началом летнего наступления армию Паулюса ожидало суровое испытание. 12 мая советские войска атаковали ее под Изюмом. Прорвав позиции 8-го армейского корпуса и разгромив венгерскую охранную бригаду, советские танковые войска оказались в 20 километрах от Харькова. Северо-восточнее города, в районе Волчанска, 6-я армия сдерживала продвижение противника и ввела в бой свои последние резервы. Спасение пришло 17 мая, когда по левому флангу Тимошенко ударил 3-й танковый корпус генерала фон Макензена. Паулюс использовал срочно переброшенные ему резервы и перешел в контрнаступление, нанеся тяжелое поражение Красной армии. 29 мая сражение за Харьков было окончено. Фридрих Паулюс получил Рыцарский крест.
1 июня 1942 года в штабе группы армий «Юг» в Полтаве командующие армиями провели совещание, на котором присутствовали Гитлер и Кейтель. Фюрер сообщил командованию группы армий о будущей грандиозной операции, в ходе которой со стороны рейха и его союзников предполагалось задействовать более полутора миллионов человек. Сначала задачей 6-й полевой армии Паулюса было обеспечить фланги танковой группировки, которая должна была наступать на Сталинград.
Чтобы улучшить для 6-й армии исходное положение, 13 июня Паулюс нанес удар по Волчанску, проведя операцию «Вильгельм», а 22 июня в ходе операции «Фридрих II» совместно с 3-м танковым корпусом взял в кольцо части Красной армии у Купянска. В Харьковском «котле» оказалась большая группировка советских войск.
Однако тут же случилось некое происшествие. 19 июня начальник оперативного отдела штаба 23-й дивизии майор Райхель после совещания в Харькове вылетел на «Шторхе» в свою дивизию. На место он не прибыл, а к ночи немецкие разведчики обнаружили самолет в 4 километрах за линией фронта. Русские обстреляли самолет, и тот совершил вынужденную посадку, майор и летчик были убиты. Разведчики принесли с собой тела двух погибших, но документов, из которых следовало, что германское командование планирует окружить и разбить части Красной армии в междуречье Дона и Волги, при майоре не нашли. 28 июня, когда вермахт пошел в наступление на Кавказ и Сталинград, Тимошенко отдал своим войскам приказ двигаться на восток. В этом документе маршал указал, что теперь, хотя и важно, чтобы враг понес тяжелые потери, основная задача — избежать окружения. Темп продвижения вермахта был впечатляюще высоким, так что полностью оторваться от преследователей советским войскам не удалось, но немцы не смогли загнать советские силы в «котел» и вели только фронтальное преследование, вступая в бои с арьергардами откатывающихся на восток дивизий противника.