А.С. Костанда происходил из греческих дворян. Окончил Ришельевский лицей (г. Одесса). С 1836 г. на военной службе в звании фейерверкера 4-го класса легкой батареи номер 1 лейб-гвардейской конной артиллерии. Золотая сабля с надписью за храбрость и орден Св. Анны 2-й степени ознаменовали заслуги командира батареи полковника А.С. Костанда в Крымской войне 1853-1856 гг. С 30 августа 1888 г. по 26 мая 1896 г. исполнял обязанности командующего войсками Московского военного округа.

До перевода в Москву - начальник артиллерии Петербургского военного округа, помощник главнокомандующего войсками гвардии и Петербургского военного округа.

Исполнял обязанности московского военного генерал-губернатора со дня назначения на эту должность великого князя Сергея Александровича и до его приезда в Москву.

Управлял первопрестольной столицей немногим более двух месяцев, издал несколько обязательных постановлений, предусматривавших наказания: для ночных сторожей и дворников - за нарушение правил уличного дежурства; извозчиков и кучеров - за неосторожную езду по улицам; владельцев торгово-промышленных заведений - за несвоевременную выдачу рабочим и служащим расчетных книжек.

Но основная его деятельность заключалась в подготовке к приезду Сергея Александровича в Москву. Прибытие в столицу великокняжеской четы ожидалось 5 мая в час пополудни. Утвержденный по случаю столь важного события особый порядок въезда предусматривал встречу в Клину, на Московском вокзале и в Успенском соборе Кремля. Передав управление города великому князю, А.С. Костанда вернулся к исполнению своих непосредственных обязанностей, не забывая при этом о благотворительности. В 1894 г. по его предложению Московский дамский комитет Российского общества Красного Креста учредил Иверскую общину сестер милосердия.

Похоронен на Тихвинском кладбище Александро-Невской лавры (С.-Петербург).