В ходе сражений в Испании проявились такие качества Шестакова, как чувство коллективизма и способность идти на самопожертвование во имя товарища. Однажды, во время воздушного боя с итальянскими «фиатами», он, не видя иного выхода, закрыл своим самолетом от пулеметного огня истребитель П. Смолякова. Лишь случай тогда спас его жизнь — две пули ударились в бронеспинку кресла, а одна прошила кожаные брюки пилота. Опешившего итальянского летчика, не ожидавшего такого маневра, били уже вдвоем.
В Испании Шестаков разработал и первые свои правила воздушного поединка. Например, при невозможности добиться преимущества в высоте он использовал бомбардировщики противника как прикрытие и атаковал вражеские истребители снизу. «Взаимовыручка товарищей в бою, их взаимопонимание — основа основ успеха, — говорил он, — действовать надо компактно и не отрываясь от группы».
Начало войны с Германией Шестаков встретил на посту заместителя командира 69-го ИАП, оснащенного истребителями И-16.
Но уже с первых дней боевых действий он фактически возглавил эту часть, расположенную под Одессой. А 16 июля он был утвержден в должности командира полка официально. К этому моменту 18 румынских дивизий вели наступление по всему фронту, и на подступах к городу разгорелись ожесточенные сражения. Шестаков выступил сторонником идеи превращения И-16 в легкие бомбардировщики и штурмовики. В августе 16 истребителей оборудовали подвесками для мелких 50-кг бомб, а также направляющими для реактивных снарядов. Вскоре импровизированные штурмовые группы уже действовали над линией фронта. 115 суток летчики шестаковского полка сражались, защищая Одессу и взлетая с аэродромов в непосредственной близости от позиций противника. 22 сентября ими была проведена наиболее удачная операция против вражеских авиабаз. Румынский пилот, сбитый незадолго до этого на PZL Р. 24, сообщил, что на базу Зельцы прибыла из Африки группа бомбардировщиков Ju 87 в сопровождении истребителей. Утром две группы полка Шестакова нанесли внезапный удар по аэродромам, уничтожив на них, по советским данным, 21 самолет противника.
В воздушных боях с истребителями Шестаков использовал собственную тактику. Боевой порядок его группы располагался несколькими ярусами по высоте — в недалеком будущем такой строй получил название «этажерка». Верхний ярус находился там, где обычно Bf 109 заканчивали набор высоты после атаки и из боевого разворота вновь пикировали на И-16. Самолеты верхнего яруса, пользуясь превосходством в скорости на снижении, могли преследовать вражеские истребители, так же как и машины среднего яруса. Нижние «ишачки» на малой высоте вынуждены были рассчитывать только на свою лучшую, по отношению к врагу, маневренность на горизонтали. В поединках с более маневренными румынскими истребителями PZL Р.24 применялась немецкая манера боя — более скоростные И-16 атаковали их сверху и тут же уходили обратно вверх.
10 сентября Шестаков получил звание Героя Советского Союза, имея на счету 3 сбитых немецких самолета лично и 8 в группе, а через месяц его полк был отведен в Крым на переформирование.
Получив истребители ЛаГГ-3, 9-й гвардейский ИАП (бывший 69-й) 15 июня 1942 года влился в состав 268-й авиадивизии, воевавшей на Сталинградском направлении. Однако в самом начале боев были потеряны сразу шесть самолетов нового типа, и пилоты разочаровались в этих машинах. Для схватки с немецкими Мессершмиттами-109 они явно не годились, так как теряли маневренность на малых высотах. Шестакову пришлось в срочном порядке разрабатывать правила применения этих тяжеловатых самолетов, личным примером претворяя их в жизнь. Он сразу отказался от оборонительного круга, который использовали «лагги» соседней части, и противопоставил немцам свой разнесенный боевой порядок, эшелонированный по высоте. Наступательная тактика позволила уменьшить потери и увеличила результативность полка. В июле 1942 года Шестаков лично сбил три Ju 88 и подбил один Bf 109. Тем не менее немецкие летчики продолжали господствовать в небе, и силы полка быстро таяли. В сентябре он вновь был снят с фронта и оснащен на этот раз более легкими истребителями Як-1. Часть пополнили опытными летчиками, имевшими на счету не менее пяти побед каждый, и перевели в особое подчинение командования 8-й воздушной армии. Борьба за господство в небе отныне становилась его основной задачей.
Под Сталинградом Шестаков почти ежедневно вылетал на боевые задания, повысив свой личный счет до 11 побед. 10 января 1943 года, взлетев с нового аэродрома близ Котельниково, он завязал бой с тремя Bf 109 и сумел сбить один истребитель. Тут же он и сам подвергся атаке — «як» загорелся, а пилот, получивший ожоги лица, был, кроме того, ранен в голову и лопатку. Посадив самолет на живот, Шестаков едва успел покинуть кабину, как его истребитель превратился в обломки после пушечной очереди «мессершмитта».