Родился Андрей Дмитриевич Федосюткин в 1913 году в с. Харланово Орловской губернии в семье лесника. Пойдя по стопам отца, окончил в 1933 году лесной техникум, и в 20 лет назначен начальником лесопункта, лесничим Дмитровского лесхоза (Орловская область). Незадолго до начала войны, в 1940 году, становится директором Дмитровского лесхоза.
В годы оккупации Курской области фашистами Андрей Федосюткин с октября 1941 по август 1942 руководил Дмитриевским партизанским отрядом, а с августа 1942 по март 1943 был комиссаром 1-й Курской партизанской бригады.
Отряд действовал на территории Орловской и Курской областей до 3 марта 1943 г. и за эти годы уничтожил более 7000 оккупантов, пустил под откос 49 вражеских эшелонов, взорвал два самолета, 12 орудий, пять автомашин, шесть км железнодорожного полотна, 48 км линии связи противника.
Все боевые операции и дни передышки комиссар Федосюткин описывал в своем дневнике. Сегодня этот уникальный документ хранится в архиве общественно-политической истории Курской области.
После войны Андрей Дмитриевич Федосюткин, как партийный и хозяйственный деятель, организовывал восстановление разрушенного народного хозяйства в Судже и Дмитриеве. В 50-е годы он возглавляет Курское областное управление лесного хозяйства. Затем работал заместителем председателя облисполкома, начальником управления легкой и пищевой промышленности, первым секретарем Льговского РК КПСС, начальником управления сельского хозяйства.
20 лет Андрей Дмитриевич Федосюткин руководил Курской областной секцией Советского комитета ветеранов войны.
Среди государственных наград, которых удостоен А.Д. Федосюткин, — три ордена Ленина, ордена Отечественной войны I и II ст., медаль «Партизану Отечественной войны» I степени и др. медали. За большие заслуги в боевой, трудовой и общественной деятельности и в ознаменование 950-летия Курска в декабре 1982 года ему было присвоено звание «Почетный гражданин города Курска».