Отец — молдаванин, бессарабский помещик, позднее разорившийся. Мать — англичанка. В семье было восемь детей — сын Александр и семеро дочерей. Семья жила в Кишинёве, затем в Одессе.
Жена — Ольга Николаевна, дочь старшего нотариуса в Твери, коллежского советника Николая Васильевича Лисицына (по другим указаниям — дочь главного нотариуса г. Твери Николая Ильича Лебедева). Окончила Высшие женские курсы в Петербурге (1899). В 1917 некоторое время возглавляла семейную нотариальную контору. Во время Гражданской войны работала в госпитале Красного Креста Добровольческой армии. Затем жила в Твери, собирала материалы о жизни и деятельности своего мужа в Сибири. В 1933 была арестована, приговорена к ссылке на три года.
Окончил Одесскую гимназию, физико-математический и юридический факультеты Санкт-Петербургского университета. Был оставлен при университете на кафедре физики для приготовления к профессорскому званию.
Работал в морском ведомстве: занимался опытами в судостроительном бассейне, связанными с определением наилучших мореходных качеств морских судов. Также преподавал физику и математику в одной из мужских гимназий Петербурга и читал лекции по электричеству в старших гардемаринских классах Морского училища.
С 1903 работал нотариусом в Твери. Входил в состав Тверского управления Российского общества Красного Креста, членом правления Тверского общества взаимного страхования, членом Совета старшин губернского общественного собрания. Был гласным городской думы, активно участвовал в деятельности существовавшего в Твери Народного университета. Являлся председателем городского комитета оказания помощи безработным. Под руководством комитета были организованы общественные работы, открыты столовые и учреждения для оказания помощи детям и семьям рабочих. Кроме того, были созданы артели: мыловаренная, кровельная, кузнечная, слесарная и др.
С 1905 — член Конституционно-демократической партии (Партии народной свободы), с 1906 — руководитель её тверской организации. По словам историка Н. Г Думовой, А. А. Червен-Водали «был человеком идеи, готовым ради неё на жертвы, неукоснительно следовавший партийной дисциплине».
В конце октября 1915 возглавил Тверской городской военно-промышленный комитет, добился получения тверскими промышленниками заказов на изготовление бомбомётов и снарядов к ним, на пошив брюк для армии, на изготовление парных повозок и подков для армии. Много внимания уделял вопросам экспорта льна из Тверской губернии, который способствовал укреплению крестьянских хозяйств, улучшению валютного рынка и стабилизации курса рубля. Руководил Тверским комитетов Союза городов по организации помощи воинам, а также городским продовольственным комитетом.
С 1 марта 1917 — председатель Временного исполкома Тверского комитета общественных организаций, преобразованного затем в губернский комитет. Занимал пост губернского комиссара Временного правительства. Ввёл вооружённую охрану основных объектов в Твери, наладил распределение продовольствия, создал городскую милицию.
В конце мая 1917 уехал в Москву, где был членом городской управы, комиссаром по благотворительным делам в Москве, работал в Торгово-промышленном союзе, входил в состав Главного комитета Союза городов. В августе 1917 был командирован Союзом городов на Юго-Западный фронт, где при его участии был восстановлен фронтовой комитет Союза.
После прихода к власти большевиков входил в состав антибольшевистской подпольной организации «Девятка», затем стал активным деятелем организаций Правый центр и Всероссийский национальный центр. 1918 уехал в Киев, а затем в Екатеринодар в расположение Добровольческой армии, где был в рамках Национального центра работал над законопроектами по аграрному, продовольственному и рабочему вопросам. Призывал отказаться от борьбы с большевиками при помощи одних штыков и принять меры, «способные убедить рабочее население в том, что возрождаемый порядок лучше большевистского». Инициировал включение в политическую платформу Национального центра пункта об обеспечении для рабочих права защиты своих профессиональных интересов с сохранением 8-часового рабочего дня для квалифицированных работников. Руководитель Екатеринодарского отделения осведомительной организации «Азбука»
В марте 1919 вместе с Н. К. Волковым и П. А. Бурышкиным был командирован в Сибирь по просьбе местных кадетов, просивших прислать в Ставку Верховного правителя России А. В. Колчака опытных организаторов, способных реализовать идею объединения фронта и тыла в единый лагерь. В июле 1919 прибыл во Владивосток, затем направился в Омск, где был принят адмиралом Колчаком. 1 августа вошёл в состав Государственного экономического совещания.
В дневнике В. Н. Пепеляева 14 октября 1919 отмечается встреча находившихся в Сибири членов Национального Центра: Волкова, Третьякова, Бурышкина, Червен-Водали, Кириллова и Пепеляева. Было решено открыть отделение центра.
В условиях кризиса колчаковского режима премьер-министр В. Н. Пепеляев предложил А. А. Червен-Водали войти в состав правительства. С 25 ноября 1919 — товарищ министра внутренних дел с возложением на него временного управления министерством. Согласился занять этот пост при выполнении ряда условий: созыва Земского собора, активного сотрудничества с земскими и городскими организациями, подчинения военных властей гражданским, передачи продовольственного дела земствам и городам, повышения роли Совета министров и смещения реакционных военных и гражданских деятелей. Условия были приняты, но наступление Красной армии и развал белой власти в Сибири не позволили наладить нормальную работу правительства. Временно принял на себя обязанности заместителя председателя правительства, пытался привлечь общественность к сотрудничеству с властью, был инициатором освобождения ряда политических заключённых.
28 декабря 1919 вошёл в состав оперативного органа государственного управления, образованного в Иркутске — так называемой «троектории» (вместе с военным министром М. В. Ханжиным и временно управляющим министерством путей сообщения А. М. Ларионовым). Вёл переговоры с руководителями антиколчаковского восстания в Иркутске в январе 1920.
Был арестован и предан суду Чрезвычайного революционного трибунала при Сибирском революционном комитете. 30 мая 1920 был приговорён к расстрелу. 10 июня ВЦИК отклонил прошение о помиловании и в ночь на 23 июня приговор был приведён в исполнение. Перед смертью попросил передать жене часы, обручальное кольцо и крест, а также прощальное письмо, в котором, в частности, писал: «Через несколько мгновений нас расстреляют, умираю за родину, которую горячо любил и к этому призываю тебя». Ольга Николаевна получила эти предметы и письмо только в 1922.