Боевое крещение Паулюса в качестве командарма состоялось под Харьковом. Тут прозвенел первый тревожный звоночек: в результате майского наступления генерала Тимошенко на город войска немецкого военачальника едва не попали в «клещи». Тогда Фридриха и его 6-ю танковую спас Эвальд фон Клейст, ударивший по ослабленному южному флангу Тимошенко. Благодаря этому армия Паулюса смогла отойти и слиться с армией Клейсга. А к 28 мая, как известно, сопротивление советских войск было сломлено, и на месте перспективной линии наступления образовался харьковский «котел», в котором оказалось 240 тысяч солдат РККА. Паулюс не только был признан одним из отцов этого локального успеха, но и награжден за вклад в победу Рыцарским крестом.
Затем командование предложило Фридриху еще раз проявить свой воинский талант. Так, его 6-я армия была поставлена на острие удара группы армий «Б», направленного на стратегически важный пункт — Сталинград. И сразу же у Паулюса возникли проблемы. Правда, на сей раз не по его вине, а исключительно из-за того, что Гитлер считал приоритетным направление на Кавказ, где двигалась группа армий «А». Из-за этого 6-я армия не шла, а буквально ползла к Сталинграду, месяцами простаивая из-за отсутствия горючего. К осени 1942 года настроение у Гитлера поменялось, и он решил, что ключевым моментом восточной кампании должен быть все-таки Сталинград. 2 сентября началась осада города. И тут злую шутку с Паулюсом вновь сыграла его нерешительность: вместо того чтобы немедленно нанести удар, как настоятельно советовали ему другие генералы, и не дать русским организовать оборону, он, прежде чем дать приказ о наступлении, несколько дней «собирался с мыслями». Возможно, именно это и стоило Фридриху исхода всей кампании. Более того, выяснилось, что Паулюс не только слабовольный командир, но еще и неважный стратег. Он бросал ударные танковые части на те участки фронта, где уместнее выглядела бы пехота: кустарники, овраги и руины города. Битва за Сталинград постепенно превратилась в затяжные уличные бои. При этом фланги 6-й армии оказались практически полностью оголенными. Командир и его танки оказались на острие гигантского выступа, протянувшегося от Дона к Волге. С севера и юга позиции прикрывали румыны, итальянцы и венгры — плохо вооруженные и не слишком боеспособные союзники. Вот как описывает боевые будни один из офицеров румынской армии: «Русские открыли ураганный огонь по левому флангу… Такого огня я еще не видел… от артиллеристской канонады сотрясалась земля и сыпались стекла. На 163-й высоте показались вражеские танки и держат путь на Распопинскую. Вскоре сообщили, что танки прошли на полном ходу через позиции и ворвались в село… Наши пушки не причинили им никакого вреда…»
Но все это не помешало Паулюсу 30 ноября 1942 года получить очередное звание — звание генерал-полковника.
Между тем, Фридрих до последнего отказывался верить в то, что дат заманить себя в западню. Он продолжат ослаблять фланги, концентрируя всю мощь армии для форсирования Волги. В середине октября в его планы коррективы внесла погода: над Сталинградом прошел ливень со снегом — все дороги моментально превратились в непролазные грязевые болота, и танки стали еще более бесполезными, чем ранее. Однако Паулюс продолжал атаковать. Но в середине ноября советские войска ударили с флангов, и мощное контрнаступление Красной Армии буквально смело оборонявшие эти рубежи венгерские и румынские части. Через несколько дней, 21 ноября, 6-я танковая оказалась в «котле». И вновь Паулюс допустил просчет: вместо того чтобы попытаться вырваться из окружения сразу, пока советские войска еще не укрепились на новых позициях (как советовали ВСЕ остальные находящиеся рядом с ним высшие офицеры), он понадеялся на помощь люфтваффе и ждал. Но помощь так и не пришла: в условиях все усложняющихся метеоусловий и угрозы нападения со стороны советских самолетов германская авиация не могла снабдить окруженных необходимыми боеприпасами и провиантом. Такая блокада незамедлительно принесла свои плоды. Немецкие солдаты не могли больше вести перестрелки с русскими, потому что им не хватало патронов. 6-я танковая стала жертвой лютых среднерусских морозов и костлявой руки голода: все лошади уже к середине декабря были съедены, и в окруженной армии стали выдавать полбуханки черствого хлеба на пятерых человек. 26 декабря один из подчиненных Паулюса сделал в дневнике такую запись: «Я бы съел и кошку. Говорят, у них вкусное мясо…» С момента окружения до конца 1942 года от холода и голода умерло 28 тысяч военных 6-й армии.