В декабре 1941 года Еременко снова встал в строй. К тому времени в битве за Москву произошел решающий перелом, и враг был отброшен от стен столицы. Советские войска перешли в наступление.
При разработке плана контрнаступления одной из задач, поставленной Ставкой, стало разобщение сильной немецкой группировки на северном направлении. Ее осуществление было поручено 4-й ударной армии, командующим которой стал Еременко. Вступив в командование 23 декабря 1941 года, уже через несколько дней ему удалось освободить ряд городов – Пено, Андреаполь, Торопец и другие – и нанести немцам значительный урон в живой силе и технике. Задача была выполнена, и в группировку немецких войск был вбит клин на 300 километров.
При проведении Торопецко-Холмской операции 20 января 1942 года Еременко вновь был ранен, получив при взрыве снаряда множественный перелом костей правой голени. Андрей Иванович отказался от отправки в тыловой госпиталь и еще в течение 23 дней продолжал руководить боевыми действиями. Только 15 февраля он был доставлен в госпиталь, где находился до августа 1942 года.
Рана еще не до конца была излечена, а Еременко 7 августа принимает командование войсками Юго-Западного фронта на Сталинградском направлении. Через три дня в его подчинение передают и Сталинградский фронт. Перед генерал-полковником Еременко была поставлена задача – удержать город любой ценой и остановить наступление немцев на западном и южном направлениях.
При обороне Сталинграда полководческий талант Андрея Ивановича Еременко проявился наиболее ярко. Он достаточно быстро мог оценивать обстановку на фронтах и принимать верные решения, вызванные требованиями обороны города.
К началу августа 1942 года немецким войскам удалось прорвать оборону на внешнем сталинградском обводе. Необходимо было провести не только срочные мероприятия по ликвидации угрозы захвата города, но и начать подготовку к дальнейшим контрударам с целью окружения и разгрома противника под Сталинградом. По указанию Еременко были собраны все имеющиеся в распоряжении фронта резервы и нанесен контрудар на юго-западном направлении. Благодаря этим действиям продвижение 4-й танковой армии было остановлено, и немцы вынуждены были перейти к обороне. На усиление немецкой группировки была переброшена 6-я полевая армия под командованием Паулюса.
При организации обороны города Еременко применял различную тактику. Так, на северо-западном направлении, для того чтобы выиграть время для создания укрепленных позиций, он организовал мощный контрудар силами авиации. В период боев на внутреннем обводе города по его распоряжению была создана специальная артиллерийская группа, что позволило быстро сосредоточивать огонь высокой плотности на наиболее опасных участках возможного прорыва противника. Кроме того, особое внимание командующий уделял разведке.
При подготовке контрнаступления Еременко настаивал на тщательной оперативной маскировке. Войска передвигались на заданные позиции только ночью, но при этом радиоточки частей оставались на прежних местах, продолжая работать, чтобы у противника создавалось мнение, что части остаются на тех же позициях. Запрещалась всяческая переписка, а распоряжения отдавались только в устной форме, причем только непосредственным исполнителям.
Наступление советских войск под Сталинградом началось 20 ноября одновременным ударом с обоих флангов. Еременко внимательно следит за развитием событий и моментально реагирует на любые изменения или задержки. После окружения немецких войск перед ним встала задача по созданию воздушной блокады окруженных немецких частей. Для этого он расположил несколько наблюдателей с рациями, которые при первых же звуках летящих самолетов передавали информацию на командный пункт. По их сигналу открывался зенитный огонь по неприятельским транспортным самолетам. Советские авиационные полки также были перебазированы на полевые аэродромы ближе к маршрутам движения немецких самолетов. Между командным пунктом и авиаполками постоянно работала связь. Такая система свела на нет все попытки люфтваффе помочь окруженным немецким дивизиям.
Благодаря умелому руководству войсками и практически мгновенной реакции на любые изменения обстановки на фронте Еременко помешал немецким частям под руководством Манштейна прорваться на помощь окруженной 6-й полевой немецкой армии.
За оборону Сталинграда Андрей Иванович Еременко был награжден орденом Суворова I степени.
1 января 1943 года по приказу Ставки формируется Южный фронт, в который вошли несколько армий Сталинградского фронта. Командование Южным фронтом принимает А.И.Еременко. Перед ним ставится задача по разгрому немецкой группировки в нижнем течении Дона с целью отрезать войска противника, находившиеся на Северном Кавказе.