После завершения Сталинградской битвы, сразу же, без перерыва, полк перешел к боевым действиям на Центральном фронте. В июне 1943 г. Константин Михаленко в числе других летчиков полка, вылетавших на разведку, наблюдал необычное оживление в районе станций Поныри и Змиевка. Автотранспорт противника с приглушенным светом большими колоннами двигался к фронту. Разгружаясь у станции, грузовики разворачивались и на максимальной скорости с включенными фарами мчались в тыл. Командованию Центрального фронта (командующий — К. К. Рокоссовский) по полученным данным стало ясно, что противник концентрирует здесь силы для наступательной операции. Оно приняло необходимые меры для усиления обороны.
Особое место в биографии К. Михаленко занимает освобождение Польши. Вопреки получившей хождение версии событий, советская авиация и, в частности, 9 Гвардейская дивизия, активно помогала польским повстанцам в Варшаве, доставляя им оружие, боеприпасы. Михаленко неоднократно вылетал на выполнение подобных заданий. 18 сентября 1944 г. он доставил в Варшаву связника-офицера Генштаба КА.
Самым опасным моментом в этих вылетах было снижение перед сбросом грузов или десантированием связистов. Город горел, дым застилал улицы, мешая различать район выброски. А ко всему прочему, по снижавшемуся По-2 сразу же открывали огонь немецкие войска, окружавшие повстанцев.
Довелось К. Михаленко принимать самое деятельное участие в осаде крепости Познань. После штурма городских укреплений советские войска подошли к цитадели. Бомбардировка ее большими силами дневных бомбардировщиков дала ощутимые результаты, но погода ухудшилась, и тогда вся нагрузка боевой работы легла на 9-ю Гвардейскую НБАД.
Входивший в эту дивизию 45-й Гвардейский (бывший 901-й) полк приземлился на аэродроме Беднары, принадлежавшем, возможно, одному из немецких авиационных училищ. В двух просеках, вырубленных в лесу, стояли учебные и боевые самолеты. Оружия было в достатке, его перенесли в отведенный под общежитие летно-технического состава двухэтажный домик, находившийся в ста метрах от леса. Разместившись на новом месте, 18 февраля 1945 г. полк приступил к боевой работе. Совершив 5 ночных боевых вылетов, стали летать на бомбардировки и днем, так как Познань находилась уже в тылу советских войск, и опасность атаки По-2 немецкими истребителями была минимальной.
Казалось бы, что мог сделать По-2 против равелинов с их многометровой толщины стенами?! Конечно, мощных бомб По-2 не поднимал, максимум — «сотки». Но и они, методично ложившиеся в одну и ту же цель, способствовали разрушению неприступных бастионов, которые до того не поддавались ни полутонным фугаскам, ни снарядам тяжелой артиллерии.
Один раз Константин Михаленко, будучи ведущим девятки, решил для повышения точности бомбометания попробовать группой сбросить бомбы с пикирования — примерно так, как это делали Ю-87. Следует сказать, что бомбить с По-2 с пикирования не разрешалось — боялись, что при отделении бомб будет повреждена поперечина между колесами. Однако перед этим заданием бомбы подвесили только на крыльевые держатели.
Уже отбомбившись, при отходе от цели вдруг увидели пару ФВ-190. Что делать в такой ситуации на По-2 с его вооружением? Михаленко маневром самолета передал: разойтись «всем вдруг». Строй бросился врассыпную, и охота за внезапно увеличившимся количеством целей для «фоккеров» чрезвычайно затруднилась. В итоге им удалось подбить только один По-2 и уже на земле зажечь его. Потерпевший бедствие экипаж был вывезен на самолете К. Михаленко, севшем у опушки леса вблизи одиноко стоявшего дома, который закрыл его от вражеских летчиков.
19 февраля одна из немецких частей, находившихся в крепости, пошла на прорыв. Положение усугублялось тем, что в этом районе еще не было сильных гарнизонов советских войск. Двигаясь лесами, немецкая часть вышла к аэродрому, где стоял 45-й Гвардейский полк. Не имевшие для сжпора противнику тяжелого артвооружения, ночники мобилизовали все свои ресурсы. Вылетая на боевые задания по бомбардировке Познани, летчики полка сбрасывали бомбы на лес, где концентрировались подразделения противника, затем совершали посадку и, после повторной подготовки самолета к боевому вылету, вылетали уже на бомбометание по крепости. А общежитие летного состава, где собрали все трофейное вооружение, стало мощным узлом сопротивления.
К исходу вторых суток немцы отказались от мысли взять аэродром «в лоб» и пошли в обход его. Экипажи 45-го полка продолжали атаковать их с воздуха. За трое суток интенсивных боев с наземным противником Михаленко совершил 28 боевых вылетов на бомбардировку крепости; при этом «подскоки» для сброса бомб на немецкие войска в районе аэродрома — в 2,5 км от полосы — длились 2–3 минуты и за боевые вылеты не считались.