8 февраля 1943 года  был призван в Красную Армию, в новосформированный 124-й пограничный полк войск НКВД СССР. Личный состав полка выполнял разные задачи в прифронтовой полосе:задерживали в освобождаемых населенных пунктах полицаев, в кубанских плавнях вылавливали казаков из немецких казачьих подразделений. Охраняли и обороняли тыл Степного фронта (ставшего 2-м Украинским): выявляли диверсантов, шпионов, дезертиров, охраняли объекты. Полк шел в арьергарде 53-й армии (II ф), зачастую оказываясь в тылу активно наступающего противника и нанося непоправимый урон его инфраструктуре и войскам. Участвовал в героической и трагической переправе  Днепра. Весной 1944 года на севере Молдавии вышли на Государственную границу СССР. Охраняли участок границы по реке Прут, уничтожая  группы отставших немцев, прорывавшихся к своим.
С момента призыва А.А. Зеленский был в звании красноармейца, в конце 1943 г. – младший сержант, командир отделения. На границе  стал старшиной заставы, минуя звания сержанта и старшего сержанта. Одновременно был комсоргом заставы. Затем занял должность заместителя начальника заставы по политчасти. В 1946 году переведен в Унгены комсоргом погранкомендатуры.
В одной из операций по ликвидации банды, напавшей на пионерлагерь, находившийся в лесу, Зеленский получил контузию от разрыва гранаты. Находился на излечении в Одессе в пограничном госпитале. 8.02.1951 года был комиссован по болезни.