Крещён в Успенской казачьей церкви Замоскворецкого сорока.
22 апреля 1849 года был принят в число кандидатов на казённый счёт Института корпуса путей сообщения в Санкт-Петербурге, который окончил в чине инженер-поручика в 1860 году.
В 1860-1867 годах - начальник отделения в IV округе пути Харьковской дороги. С ноября 1867 года - помощник начальника 2-й дистанции Московско-Тульского участка Курской железной дороги. В 1868 году назначен начальником Московско-Курской железной дороги; в связи с временным преобразованием корпуса инженеров путей сообщения из военного в гражданский переименован в коллежского асессора по старшинству.
В 1871 году Правительствующим Сенатом произведён в надворные советники. Приказом по Министерству путей сообщения назначен младшим помощником инспектора Московско-Курской железной дороги, в 1873 году - помощником инспектора. В 1874 году произведён в коллежские советники.
В 1875 году назначен управляющим Орловско-Грязской железной дороги. В 1880 году назначен младшим инспектором Центральной инспекции железных дорог, созданной с целью обеспечения безопасности движения. В 1881 году произведён в статские советники за выслугу лет.
19 сентября 1883 года приказом по Министерству путей сообщения № 79 был назначен начальником службы пути Екатерининской железной дороги. Министр путей сообщения России адмирал К. Н. Посьет рекомендовал А. А. Верховцева на должность начальника Екатерининской железной дороги как опытного и грамотного инженера, кавалера орденов Св. Анны и Св. Станислава. Кандидатуру утвердил император Александр III. С 1 июля 1893 года по 1 января 1894 года одновременно заведовал Донецкой железной дорогой в связи с переходом её в казённое Управление.
Плодотворная трудовая деятельность А. А. Верховцева на посту начальника Екатерининской железной дороги не осталась незамеченной. В мае 1886 года ему была объявлена искренняя благодарность Министра путей сообщения за труды и распорядительность при следовании Императорских поездов. А. А. Верховцев был удостоен личной аудиенции императора и награждён памятным подарком из императорского кабинета - перстнем и брошью с бирюзой и бриллиантами. За отличие по службе он был произведен в действительные статские советники и тайные советники.
Возглавлял Екатерининскую железную дорогу до своей смерти.
Скончался 18 ноября 1900 «от мозгового удара». Был похоронен управлением Екатерининской железной дороги и губернатором города с подобающими почестями в ограде Покровской церкви, рядом с вокзалом станции Екатеринослав. На могильной плите было начертано: «Здесь покоится первый начальник и устроитель Екатерининской железной дороги, почивший на 63-м году жизни».
В первую годовщину его смерти управление заказало в Покровской церкви панихиду и приняло решение назвать одну из станций в честь первого начальника дороги (см. «Память»). В годы Великой Отечественной войны Покровская церковь была разрушена; после войны прах А. А. Верховцева перезахоронен на кладбище возле Преображенского собора. В 1967 году городские власти воздвигли на этом кладбище монумент революционерам и старым большевикам, героям Великой Отечественной войны, вследствие чего другие могилы, в том числе могила А. А. Верховцева, не сохранились.
ДостиженияВ течение года Орловско-Грязская железная дорога, пребывавшая в аварийном состоянии, под умелым руководством А. А. Верховцева была приведена в порядок. Уже в ноябре 1876 по МПС ему была объявлена благодарность за «Содействие в исправном ее содержании».
За 7 месяцев 12 дней первого года эксплуатации (1884) валовая выручка Екатерининской железной дороги от перевозки пассажиров и грузов почти покрыла расходы по эксплуатации дороги, дав «дефициту лишь 9 049 руб. при общем расходе в 744 880 руб.». В 1885 железная дорога дала уже значительный чистый доход - 245 692 руб. 49 коп., а в 1888 - 1 205 000 руб. На десятом году эксплуатации железной дороги чистый доход составил 2 780 119 руб. 07 коп. (6,53 % чистой прибыли на затраченный капитал).
В 1884 году была начата и в декабре того же года закончена и открыта для эксплуатации Богодуховская ветвь (20,21 версты) от ст. Ясиноватая к Богодуховским каменноугольным копям. По данным 1893 года она принесла 439 000 руб. валового и 138 000 руб. чистого дохода. В декабре 1889 было открыто движение по Кальмиусской ветви, обслуживающей Мушкетовский угольный район.
Всего за 1884-1894 годы было построено 42,08 версты железнодорожных путей.
А. А. Верховцев успешно аргументировал перед правительством необходимость строительства участка Чаплино-Бердянск, который досрочно был открыт для регулярного движения 26 декабря 1898 года.
К 1900 году, завершению трудового пути А. А. Верховцева, в зоне обслуживания магистрали действовало 770 промышленных предприятий, 184 угольные шахты, 57 рудников, 47 кирпичных заводов, 255 предприятий по переработке продукции сельского хозяйства. Население Екатеринославской губернии увеличилось в два раза, а города Екатеринослава - в три раза.