15 декабря 1941 года подполковник Андрей Яковлевич Веденин назначается командиром 118-й стрелковой дивизии. Андрею Яковлевичу было поручено сформировать и подготовить к боевым действиям новую дивизию из призывников Костромской, Кировской и Горьковской области. Местом сбора была избрана Шахунья. Средний командный состав дивизии прибывал из военных школ и училищ. Одним из немногих, кто  имел боевой опыт, стал полковой комиссар Платон Иванович Петров. Назначались в командование и люди с опытом партийной работы. Начальник политотдела дивизии Кирилл Евтихнеевич Захаренко раньше был секретарем райкома партии.

После завершения формирования 118-я стрелковая дивизия участвовала в Ржевско-Вяземской наступательной операции, в наступлении на Погорелое Городище и Зубцов. С 20 апреля ее части в составе армии перешли к обороне восточнее Зубцова. В июле — августе 1942 г. в ходе Ржевско-Сычевской наступательной операции дивизия форсировала р. Вазуза южнее Зубцова и обеспечила тем самым успешное продвижения войск 29-й армии с севера и соединение с войсками 30-й армии юго-восточнее Ржева. С 26 сентября полковник А.Я. Веденин находился в госпитале после ранения.

После выздоровления с начала ноября командовал 118-й стрелковой дивизией. В марте дивизия успешно действовала в Ржевско-Вяземской наступательной операции. Прорвав оборону противника, ее части преследовали его вплоть до Дорогобужа. За отличие в этих боях в апреле 1943 г. она была преобразована в 85-ю гвардейскую. 

3 августа 1943 года Андрей Яковлевич Веденин был переведен из 85-й дивизии  командиром в 71-м стрелковый корпус и воевал на Западном, затем 3-м Белорусском фронтах.