22 июня 1941 года, поднятый по тревоге взвод, которым командовал лейтенант Павел Гудзь, (пять тяжелых танков «КВ-1», двух средних — «Т-34» и два бронеавтомобиля), двигался в направлении Западной границы в авангарде боевых порядков. Встретив на пути немецкие силы, Гудзь отдал приказ с ходу атаковать их. Взвод Гудзя подбил пять немецких танков, три бронетранспортёра и несколько автомашин. В тот же день командирский «КВ-1» под управлением механика-водителя Галкина (в прошлом — испытателя танков Кировского завода в Ленинграде) нанёс скользящий удар в направляющее колесо вражескому танку «Pz Kpfw III», сбил с него гусеницу и сильным ударом свалил в кювет. Согласно некоторым источникам, это был первый танковый таран в дивизии, а возможно, и во всей Красной Армии. За этот первый бой лейтенант Гудзь был представлен к ордену Красного Знамени.
До конца июня 32-я танковая дивизия защищала направление Львова. Прикрывая отход танковой колонны через город, Гудзь со своим экипажем уничтожил 5 танков и вновь был представлен к ордену Красного знамени, который, как и в первом случае, не был ему вручен.
В июле 1941 года 32-я дивизия участвовала в обороне Бердичева; а в конце месяца попала в окружение под Уманью. В августе остаткам дивизии удалось пробиться к своим. Дивизия была расформирована. Лейтенант Гудзь был зачислен начальником штаба 89-го, вновь сформированного, отдельного танкового батальона. Для получения новой техники он выехал в Москву. Пять танков «КВ» из состава батальона стали участниками знаменитого парада 7 ноября 1941 года, продемонстрировавшего всему миру стойкость Советского Союза. Одним из танков командовал лейтенант Гудзь. Враг был в опасной близости от столицы, но парад всё же провели, а участвовавшая в нём техника с парада сразу же пошла к линии фронта.
В начале декабря после непрерывных, ожесточенных боев в батальоне Гудзя остался лишь один «КВ-1», который и вступил в сражение с немцами.
Противник на этом участке располагал 20 танками, четырьмя батареями полевых орудий и примерно двумя батальонами пехоты, имея численный перевес над обороняющимися советскими частями. По предложению лейтенанта Гудзя его танк был поставлен в засаду за небольшой кустарник поодаль от позиций своей пехоты, находящийся в прямой видимости врага. Это было рискованным вариантом, но решили поступить именно так.
Тем временем советская артбатарея вела усиленный огонь в направлении противника, чтобы дать возможность советскому танку незамеченным добраться до планируемой позиции, невдалеке от противника. Впереди просматривалось село и силуэты вражеских танков. Ближе к рассвету Гудзь приказал экипажу приготовиться. Наводчик взял в прицел передний немецкий танк, стоящий на улице села. Спустя несколько секунд раздался первый выстрел и вражеский танк загорелся. Оказалось, в нём, как и в других, не было экипажа — немцы настолько беспечно и самоуверенно чувствовали себя рядом с советскими позициями, что не организовали дежурство. «КВ» продолжал стрелять, подбил еще два вражеских танка. Из домов в панике выскакивали ошеломлённые немецкие танкисты и бежали к своим машинам, но радист, сидевший за пулемётом «КВ» был готов к этому. Выстрелы из пушки смешались с треском пулемёта, поливавшего огнём высыпавшую из домов вражескую пехоту и танкистов.
Многим вражеским танкистам удалось добраться до своих машин, орудия которых стали разворачиваться в сторону советского танка. Послышались ответные выстрелы, один из снарядов попал в башню ««КВ»», но отскочил рикошетом. Гудзь приказал, не останавливаясь, продолжать огонь. Немцы уже сориентировались и отвечали плотным пулемётно-пушечным огнём, но броня выдерживала выстрелы их орудий. Советская пехота, пытаясь поддержать танкистов, перешла в атаку на село. Три часа длился бой и завершился полной победой советских войск. Гудзь записал на свой счёт ещё десять подбитых вражеских танков. «КВ» получил 29 попаданий, но превосходство в бронировании советских танков над немецкими в 1941 году было слишком очевидным, чтобы удивляться тому, что ни один из этих снарядов броню «КВ» не пробил. За бой у села Нефедьево Гудзь получил орден Ленина.
Весной 1942 года Павел Гудзь становится заместителем командира батальона, который вскоре будет расформирован. В то же самое время он получает звание капитана и назначается на должность командира 574-го танкового батальона, а осенью этого года, уже в звании майора, является заместителем командира 8-го отдельного Гвардейского танкового полка прорыва.
Под Сталинградом Гудзь получил тяжелое ранение. Его танк в бою был подбит противником, а самого Павла едва вытащили из горящей машины вовремя подоспевшие товарищи. Однако весной сорок третьего, после госпиталя, Гудзь снова на передовой в составе 5-го гвардейского танкового полка прорыва. Осенью, уже в звании подполковника он становится командиром соединения.