Родился 8 августа 1908 года в деревне Красново Исетского района Тюменской области. В 1937 году переехал с семьей на постоянное место жительства в город Тюмень. Работал приемщиком на Тюменском комбинате хлебопродуктов. 

В 1941 году был призван в Красную Армию Тюменским РВК Омской обл. В 1942 году попал на фронт. Погиб от ран 26 августа 1943 года в госпитале города Ленинграда (были перебиты обе ноги). В одном из наградном листе было указано, что до этого было 2 ранения.

В похоронке, которую получила его семья, говорилось, что "умер от ран 36 августа 1943 года и  захоронен на Мемориальном Пискаревском кладбище города Ленинграда в братской могиле № 85."

Были найдены рассекреченные приказы:

по 191 Краснознаменной стрелковой дивизии от 13 февраля 1943 г. Действующая армия: От имени Призидиума Верховного Совета Союза ССР, за образцовое выполнение боевых заданий командования на фронте борьбы с немецкими захватчиками и проявленные при этом доблесть и мужество Награждаю "Медалью за отвагу" красноармейца Столбова Андрея Никитовича - Стрелка Отдельного Учебного батальона. 

Из Наградного листа: "Тов. Столбов в бою за родину в районе "круглая роща" ... проявил мужество и отвагу, он всегда как лучший красноармеец, шел впередии уничтожал немцев. С лозунгом За Родину! За Сталина! убил 3-х немцев, взял трофейный ручной пулемет. Будучи связным он всегда аккуратно точно и в срок выполнял все приказания и чем помогал управлению боем и в самых трудных условиях боя, он под громом артиллерийского огня пробирался на передний край и доставлял приказания. Достоин правительственной награды "Орден Красной Звезды". /Командир отделения Учебного батальона Капитан Ковалев/"

Приказ № 017/Н219 стрелковому полку II стрелковой дивизии 27 июля 1943 г. Действующая армия от имени Президиума Верховного Совета Союза ССР Награждаю Медалью "За боевые заслуги": Наводчика минометного расчета мл.сержанта Столбова Андрея Никитича за то, что он в бою 25.07.1943 года в районе Рабоч.поселка №6 - Синявино вместу со своим расчетом поддерживал минометным огнем наступающую пехоту. Расчет уничтожил 1 огневую точку противника.