Учился в школе на станции Красный Рог, где окончил 4 класса. В 1937 году переехал к родным матери в Брянск, там закончил среднюю школу и в 1941-м вернулся в Красный Рог. От фашистов Красный Рог освободили в 1943 году. Осенью этого же года Анатолия призвали в ряды Красной Армии. Ему было всего 18, он был молод и неопытен. С группой войск новобранцы пешком дошли до Унечи, а оттуда их отправили на Урал. Там молодых воинов обучили технике боя и в 1944 году отправили на фронт. Из поезда высадили в Каунасе, который к этому времени уже был освобожден. Сражался Анатолий Лукьянович на передовой. Спустя месяц в одном из боев он был ранен, и его отправили в госпиталь. Вернувшись, Анатолий Лукьянович участвовал в освобождении литовских городов и деревень. Сражался на 3-м Белорусском фронте. В 1945 году Анатолия Лукьяновича снова тяжело ранили. Он потерял сознание и очнулся только в медицинской палатке. Снова его отправили в госпиталь, на сей раз в Рязань, где его и застала весть о Великой Победе. Это был яркий, солнечный день. Казалось, радовалась вся земля: и люди, и животные, и даже растения. В 1945 году после победы Анатолий демобилизовался и вернулся в родной Красный Рог. Надо было входить в ритм мирной жизни. А с чего начать? Специальности нет, работы тоже нет. Поэтому Анатолий Лукьянович решил пойти учиться и поступил в Новозыбковский торгово-кооперативный техникум, окончив который в 1949 году, по распределению поехал работать в Новодугинский район Смоленской области. Работал плановиком, заместителем председателя правления Новодугинского райпотребсоюза. Здесь он познакомился со своей второй половиной, Лидией Гурьевной. В 1951 году Анатолий Лукьянович вернулся в Красный Рог, а затем переехал в Минск. Из Минского облпотребсоюза его направили в Заславль. Анатолий Лукьянович работал в Заславском райпотребсоюзе плановиком, заведующим магазином. Позже Белкоопсоюз направил Анатолия Лукьяновича на работу в Лунинец товароведом Лунинецкого райпотребсоюза. В 1954 году, после того как Пинская область была присоединена к Брестской, Анатолий Лукьянович снова вернулся в Заславль и 20 лет проработал завторгом в местном горпо. Но старые раны стали напоминать о себе, и Анатолий Лукьянович перешел работать диспетчером магазина «Стройматериалы». О смелости и героизме Анатолия Лукьяновича Милехина, проявленных на войне, говорят его боевые награды: орден Отечественной войны 1-й степени, медали «За отвагу», «За боевые заслуги», «За победу над Германией», а также юбилейные медали. За трудовые заслуги награжден медалями «За доблестный труд», «Ветеран труда», значком «Отличник Советской потребительской кооперации». А.Милехин занесен в книгу «Ветераны потребительской кооперации Республики Беларусь».