А. А. Авдеев родился 12 марта 1819 года в семье помещика Александра Алексеевича Авдеева из Тульской губернии и Марии Петровны Авдеевой (в девичестве — Рейхенбах), принадлежавших к дворянскому роду Авдеевых. С 1831 года проходил обучение архитектуре под руководством архитектора П. Н. Соболевского в 1-й Московской гимназии. По просьбе архитектора М. Д. Быковского в 1843 году был направлен к нему помощником. В 1850 году получил право на производство строительных работ по гражданским сооружениям и был назначен младшим архитектором Попечительского совета заведений общественного презрения в Москве (фактически состоял в этой должности с 1848 года). В 1851 году Авдеев отправился, с целью изучения художественных памятников, в Германию, Францию и Италию, откуда сообщал свои наблюдения и впечатления в «Московские Ведомости» и в сборник профессора Леонтьева «Пропилеи».
В 1853 г. находился при археологических раскопках на Таманском полуострове и занимался срисовыванием найденных там древностей. Составил проект здания астрономической обсерватории Московского университета, которое и было построено им в 1854 году по этому проекту (Нововаганьковский переулок, 5).
В 1855 году вышел в отставку. Поселясь в Крыму, построил:
В 1865 году стал одним из основателей Московского архитектурного общества. В 1871 году Императорская Академия художеств возвела его в академики без требования от него исполнения особой программы.
Умер в 1885 году в Санкт-Петербурге, куда прибыл по делам строительства храма.