Восьмого апреля 1944 года 4-й Украинский фронт перешел в наступление. В ночь на 11 апреля начала наступление Отдельная Приморская армия, развернувшая преследование противника по всему фронту. Утром 12 апреля войска Еременко освободили Керчь. Затем, прорвав оборону врага на Ак-Монайских позициях, на следующий день в районе Карасубазара они соединились с частями 4-го Украинского фронта. 13 апреля был освобожден Симферополь. В течение трех следующих дней части Отдельной Приморской армии по юго-восточному побережью Крыма продвигались к Севастополю, готовясь к штурму сильно укрепленного города. Освободив в кратчайший срок Южное побережье Крыма — почти 420 километров от Керчи до Севастополя, — Приморская армия спасла от разрушения его прекрасные здравницы. В ходе этих боев Андрей Иванович снова был ранен, но на этот раз легко.
Восемнадцатого апреля 1944 года А. И. Еременко был назначен командующим 2-м Прибалтийским фронтом. Возглавляемые им войска нанесли мощный удар на Идрицко-Режицком направлении и вышли на подступы городов Остров, Идрица, Пушкинские Горы. В июле 1944 года войска фронта успешно провели Режицко-Двинскую операцию, в ходе которой они продвинулись на запад на 200 километров. «За умелое руководство войсками и проявленные в боях с немецко-фашистскими захватчиками мужество и героизм» Указом Президиума Верховного Совета СССР от 29 июля 1944 года генералу армии А. И. Еременко присвоено звание Героя Советского Союза.
В августе 1944 года 2-й Прибалтийский фронт, развивая наступление вдоль северного берега реки Западная Двина, продвинулся еще на 60–70 километров, освободив крупный железнодорожный узел — латышский город Мадона. О том, какие трудности пришлось преодолевать войскам в ходе этого наступления, Еременко рассказал в своей статье, опубликованной во фронтовой газете «Суворовец» (№ 199; август 1944): «Наши воины стремительно двинулись вперед на Рижском направлении и преодолели известные своей непроходимостью Лубанские болота… Переход через Лубанские болота есть выдающийся воинский подвиг. На этой гнилой местности, протянувшейся на десятки километров, считалось невозможным вести боевые действия, тем более крупными соединениями. Однако войска фронта за десять дней прошли с боями Лубанскую низменность, сбивая врага с оборонительных рубежей, совершая тяжелые обходы по непролазным топям и сбрасывая врага с дорог. Наши герои-гвардейцы шли по наспех проложенным гатям, пробирались вперед по пояс, а то и по горло в болотной воде, перетаскивая на себе свое оружие, — и победили. Честь и слава бойцам и офицерам лубанского перехода. Его участники — бойцы и сержанты — не уронили престиж доблестного русского солдата, известного со времен Суворова тем, что для него нет непреодолимых преград. Участники перехода — офицеры — показали такое искусство маневра в сложнейших природных условиях, которым можно по достоинству гордиться. В Лубанах приумножена гвардейская слава!»
Пришло время сражений совершенно другого рода. Теперь это были бои по преследованию противника и от командующего требовалось провести анализ управления войсками, чтобы повысить эффективность наступательных действий и взаимодействия всех служб и родов войск. И вновь первое, на что обратил внимание Еременко, была работа разведки. Ее организация в период преследования противника является сложным и кропотливым делом, поэтому, несмотря на то что она находилась под неослабным контролем фронтового управления, не удалось полностью избавиться от некоторых недостатков, особенно в корпусном и дивизионном звене. Нередко нарушалась столь необходимая непрерывность в действиях разведки. Система огня противника на переднем крае и особенно в глубине подчас выявлялась не полностью, поэтому артиллерии приходилось иногда вести огонь не по целям, а по площадям, что приводило к большому расходу боеприпасов при снижении эффективности. Были случаи, когда отход противника обнаруживался слишком поздно. Командиры ряда частей и подразделений не проявляли достаточной инициативы по быстрому реагированию на изменение ситуации, когда от них требовалось осуществить в сжатые сроки смелый маневр. Также командиры явно недостаточно использовали для ведения боя темное время суток. Действия групп и подразделений в тылу противника были, к сожалению, не всегда достаточно успешными.