Алексей Иванович вспоминал: «Осенью 1929 года участвовал в боях на КВЖД в должности командира огневого взвода 3-й гаубичной батареи. Бои проходили под Маньчжурией и Далайнором. Это было первое мое боевое крещение. В боях я почувствовал мощь и действенность огня своей батареи. Приходилось вести огонь не только с закрытых позиций, но и дважды прямой наводкой картечью, отражая контратаки противника. Я был горд, что служу в таком грозном роде войск, каким является артиллерия. 20 ноября в районе Абагатуйского разъезда пришлось вступить в рукопашную схватку в конном строю с белокитайской конницей. Эти эпизоды послужили серьезным уроком и экзаменом в бою. За эти бои приказом командующего ОКВД тов. Блюхера был награжден ценным подарком и памятным значком КВЖД».
В 1930 году Нестеренко служил командиром взвода полковой школы, командиром топографического отряда полка. В 1931 году был назначен курсовым командиром Томской артиллерийской школы с присвоением внеочередного звания и служил там в должностях командира мензульного и теодолитного взвода топографической батареи (в 1932 году он поступил на курсы низшей геодезии при Томском университете, где учился без отрыва от службы, и успешно окончил эти курсы в следующем году), первым помощником начальника штаба дивизиона, командиром батареи до поступления в 1936 году в академию.
Военной службе помогали хорошая физическая форма, занятия разными видами спорта. Нестеренко был чемпионом Сибирского округа 1934 и 1935 годов по военному многоборью. Он писал: «Для меня лыжи — родная стихия. Еще в 1935 году я возглавлял тысячекилометровый пробег отряда курсантов Томского артиллерийского училища. Расстояние в 1070 километров мы прошли за 11 ходовых дней. Средний суточный переход составил 97 километров. К финишу прибыли без единого отставшего. Этот переход был отмечен приказом наркома обороны К. Е. Ворошилова».
Участники пробега тщательно отбирались. К 1 февраля 1935 года все тренировки, начиная от массовых, в которых участвовала вся школа, и, кончая 200-километровым пробегом в Анжерку, когда был отобран основной состав команды, закончились. Лыжники, включенные в группу, на тренировках к началу большого перехода уже прошли 1083 километра.
Переход оказался намного труднее, чем ожидалось. Лыжников с самого начала взяла в оборот суровая сибирская погода. Лютый мороз сменялся снежными метелями, на смену им приходила такая оттепель, что на лыжи налипали пудовые комья снега. Во время этого лыжного перехода проявились лучшие человеческие качества Алексея Ивановича. Вот только один из эпизодов: целый день группа поднималась к перевалу. Лютовал мороз. Люди шли из последних сил. Труднее всего пришлось Нестеренко — ведь ему часто приходилось прокладывать по снежной целине лыжню. Смеркалось. До населенного пункта, где намечалась ночевка, оставалось километров десять, когда сзади по цепи доложили: «Отстал курсант Кочетов». Нестеренко остановил колонну. «Кому идти на помощь товарищу?» Взгляд Алексея скользил вдоль колонны. Его самого переполняла гудящая усталость. Он представил, что то же самое испытывает каждый из тридцати шести человек, стоящих в строю. И командир сам повернулся лицом к обжигающему ветру и отправился на помощь отставшему. Он исходил из того, что был самым подготовленным среди участников пробега. Так и всю свою жизнь Алексей Иванович брал все самое трудное на себя.
«ПРИКАЗ НАРОДНОГО КОМИССАРА ОБОРОНЫ СОЮЗА ССР
№ 54
18 марта 1935 года, г. Москва
Отряд Томской артиллерийской школы в составе 30 пеших лыжников и 8 конных лыжников со станковым пулеметом на специальной установке, с полным комплектом боеприпасов и снаряжением прошел от Томска до Новосибирска 1071 километр за 11,5 ходовых дней, имея всего две дневки.
Пробег проходил в трудных условиях. Ввиду оттепелей отряд несколько переходов шел по ночам. Несмотря на это, отряд 21 февраля блестяще финишировал в Новосибирске. Техническая и медицинская проверка на финише показала вполне бодрое состояние личного состава, исправность оружия и снаряжения, отсутствие потертостей и отставших.
Отмечая работу командования школы в организации и проведении данного пробега, начальнику Томской артиллерийской школы т. Сергееву объявляю благодарность.