Путь Лещенко к главной должности его жизни очень похож на путь миллионов его ровесников. К моменту его призыва на действительную службу он окончил поселковую школу и выучился на паровозного машиниста. Опыт работы с механизмами наверняка сыграл свою роль, кроме личного желания, в его призыве в декабре 1928 г. на Черноморский флот, по терминологии того времени — Морские силы Черного моря. Учитывая немалую по тем временам техническую подкованность краснофлотца Лещенко, его направили в объединенную школу артиллерийских старшин учебного отряда флота. А по ее окончании в августе 1929-го назначили на башенную батарею береговой обороны № 35. Здесь за 10 последующих лет довелось ему пройти путь от номерного в отделении подачи боеприпасов до командира батареи.
Одна из главных причин — неутолимая жажда знаний молодого краснофлотца. «Мощная боевая техника меня очень привлекла так, что я и в свободное время старался прочитать описание и просмотреть чертежи, чтобы быстрее овладеть техникой, изучить детально ее действия. И я старался как можно быстрей ее освоить и научиться ею быстрее управлять», — вспоминал Лещенко{429}.
Уже через несколько недель он стал комендором-наводчиком, а еще через непродолжительное время — командиром правого орудия 2-й башни. Такую должность обычно занимали старшины с многолетним опытом службы.
В декабре 1931 г. срочная служба Лещенко подошла к концу, и когда командир батареи, а им был будущий флагманский артиллерист ЧФ А. А. Рулль, предложил Алексею остаться на сверхсрочную, тот не упирался и не раздумывал. И вот Лещенко — уже старшина 1-й башни. Он хочет расти, учиться дальше, но рапорт с просьбой о направлении на параллельные курсы при военно-морском училище ему вернули: нужен на батарее. Экзамены же предложили сдать экстерном. Сочетать службу и учебу было сложно. Но организованность и упорство дело свое сделали: в 1934-м, сдав необходимые экзамены, Алексей Лещенко становится средним командиром РККФ и получает назначение помощником командира 1-й башни.
На батарее он был единственным из лиц командного состава, не окончивший военно-морского артиллерийского училища. А отставать от своих товарищей Алексей не хотел. Вот и усиленно совмещал самоподготовку с выполнением служебных обязанностей и работой с личным составом. Через два года он получил третью по значимости (после командира и военкома) должность на 35-й ББ — помощника командира. Если проводить аналогию с боевым кораблем — Лещенко стал старпомом, да еще такой грозной крепости, притом не имея высшего образования. У артиллеристов такой служебной категории это было редкостью. В полной мере происшедшее осознавал сам Алексей Яковлевич. «У меня, как у помощника командира батареи, работы было много: организация повседневной и боевой службы, организация боевой подготовки, ведение хозяйства батареи — все это лежало на мне. От того, как работает и разворачивается помощник командира батареи, зависит ход боевой подготовки и организация службы на батарее», — писал он без всяких преувеличений{430}.
В своих воспоминаниях Лещенко неизменно с уважением и благодарностью отзывался о людях, с чьей помощью рос в профессиональном отношении. Его добрая память о командирах батареи, под началом которых ему довелось служить — Е. П. Донце, И. Ф. Кабалюке, А. А. Рулле и П. А. Моргунове (в 1941–1942 гг. — начальник береговой обороны ЧФ и СОР, генерал-лейтенант), многое говорит о человеческих качествах Алексея Яковлевича.
Служба спорилась, однако наступил 1937 г., по всей стране ширилась кампания по выявлению «врагов народа», доносы множились, эта мутная волна накрыла и Лещенко. В компетентные органы поступила порочащая помощника командира секретного объекта информация: его отец — якобы бывший царский офицер и служил в белой армии, а его родственником является известный в эмигрантской среде певец Петр Лещенко. Донос свою подлую роль сыграл: Лещенко исключили из партии и уволили со службы.
Моряк не смирился, толкался во все партийные двери флота, а затем обратился с жалобой в ЦК ВКП(б). Видно, не черствой душе попала она в руки. Из Москвы пришло предписание тщательно разобраться в ситуации. Парткомиссия флота направила одного из своих членов на родину Лещенко, и собранный им материал позволил отклонить все наветы. Решение парткомиссии батареи было отменено, и Лещенко восстановили в партии. Сразу сдвинулся с места и вопрос восстановления на службе. Алексею предложили вернуться на ранее занимаемую должность, но молодой командир выдвинул свои резоны против. Не хочу, заявил он, чтобы люди, которые ранее видели в нем «примазавшегося к партии», теперь, ощутив его требовательность и взыскательность, воспринимали их как придирки и попытки свести счеты. Командование согласилось, и Лещенко был назначен командиром батареи 122-мм орудий.