В Красной Армии с 1940г.

Вероятно, окончил 53 ОШМАС (окружная школа младших авиаспециалистов) Забайкальского военного округа.

В мае 1941г. красноармеец Клименков находился в Читинском окружном военном госпитале ВГ 321 (причина не указана). Выписан 23 мая 1941г.

С мая 1943г. в составе 32 отдельного разведывательного авиаполка. Командир полка подполковник Щенников Николай Павлович.

02 июня экипаж: летчик младший лейтенант Скоков Василий Васильевич, летнаб младший лейтенант Хрусталев Павел Иванович (18 августа 1945г. присвоено звание Герой Советского Союза, посмертно), Клименков выполнил разведку в районах Зубков, Болхов, Орле, Мценск.

Следующий боевой вылет экипажа: 03 июня.

17 июня 1943г. полк был преобразован в 99 отдельный гвардейский разведывательный авиаполк.

К июлю 1943г. гвардии сержант Клименков совершил 10 успешных боевых вылетов.

Приказом от 03 июля 1943г. был награжден медалью «За отвагу».

17 июля экипаж: летчик младший лейтенант Михайлов, летнаб сержант Усков Иван Семенович, Клименков- выполнял разведку дорог в районах Карачев, Болхов. Был атакован парой истребителей Ме-109 (Мессершмитт). Огнем истребителей был поврежден правый мотор.  Перейдя линию фронта, в районе Арсеньево был атакован своим истребителем. Уходя на одном моторе с потерей высоты, совершил вынужденную посадку в районе Скуратово. При посадке летчик получил тяжелые травмы головы. Самолет переломлен пополам. 

06 декабря экипаж: летчик гвардии лейтенант Гатауллин Анвар Анварович (18 августа 1945г. присвоено звание Герой Советского Союза), летнаб гвардии лейтенант Устинов Федор Степанович, Клименков, выполнив тренировочный полет, при посадке промазал и вкатился в лес. Самолет встал на нос.  Самолет требует ремонта, экипаж невредим.

К концу 1943г. совершил 26 успешных боевых вылетов. Приказом от 17 января 1944г. гвардии старший сержант Клименков был награжден орденом Красной Звезды.

08 января 1944г. экипаж Гатауллин, Устинов, Клименков выполнял специальное задание по фотографированию железной дороги на участке Новосокольники- Идрица. Под зенитным огнем противника, впервые в полку, полет был совершен по прямой. В районе Идрица был атакован немецким истребителем. В воздушном бою погиб гвардии лейтенант Устинов.

28 февраля экипаж: Скоков, Хрусталев, Клименков выполнил разведку районов Опочка, Есенники, Пустошка, Щукино. 

Приказом от 13 июня 1944г. Анатолий Алексеевич награжден орденом Отечественной войны II степени.

К началу октября 1944г. совершил 68 успешных боевых вылетов.

Приказом от 05 ноября 1944г. награжден орденом Славы III степени.

14 января 1945г. экипаж: командир полка гвардии подполковник Щенников, штурман полка гвардии майор Баранов Николай Васильевич, стрелок-радист Клименков- выполнил разведку в районах Апшуцизме, Роя, Видале, Мерераге (побережья Рижского залива). В районе Видале сбросил 2 авиабомбы ФАБ-100 и 30000 листовок.

18 января экипаж выполнил разведку в районах Таиси, Кулдига, Скрунда, Тукуме. На аэродром Крумули сбросил 2 авиабомбы ФАБ-100 и и 30000 листовок. На аэродроме был впервые обнаружен Юнкерс-88.

09 апреля экипаж фотографировал районы Сапдуе, Скрунда. В районе Сапдуе сбросил 2 авиабомбы ФАБ-100.

15 апреля выполнил разведку передвижения войск по железным и шоссейным дорогам, сфотографировал аэродромы Оксне, Каркиес, бухты Роя, Энгуре, Мазирбе. В районе Тукумс сбросил 2 авиабомбы ФАБ-100 на повозки противника.

За время войны Анатолий Алексеевич совершил 82 успешных боевых вылетов.

Приказом от 11 мая 1945г. награжден орденом Отечественной войны I степени.

Награжден медалями «За взятие Кенигсберга»,  «За победу над Германией в Великой Отечественной войне 1941-1945 гг.».