Учился в Киевском и Санкт-Петербургском университетах по юридическим факультетам. Ещё студентом издал первый том «Сказаний иностранных писателей XVI века о России» (1841), на латинском языке; за ним последовал второй, под заглавием: «Historiae Rathenicae Scriptores exteri saeculi XVI» (1842). Он перевел на французский язык российский торговый устав, сделал извлечение из русских законов об иностранцах («Die russischen Gesetze Auslander betreftend»), собрал вБерлинской публичной библиотеке коллекцию портретов и автографов разных исторических лиц, часть которой была издана под заглавием «Galerie slave» (до 360 деятелей славянских, с биографиями), разыскал реляции бранденбургскихпосланников о России в XVII столетии, копии с которых поступили в архив Министерства иностранных дел, составил подробный каталог русских и иностранных материалов для истории России, извлеченных из архивов и библиотек Западной Европы.

С 1843 года Старчевский был сотрудником «Журнала Министерства Народного Просвещения» по исторической критике и славянской этнографии и филологии; составил грамматики десяти славянских наречий (в рукописи) и напечатал: «Литература русской истории с Нестора до Карамзина» («Финский Вестник»), «О заслугах, оказанных государственным канцлером Н. П. Румянцевым», «Жизнь Н. М. Карамзина» (Санкт-Петербург, 1845). В 1848—1853 годах Старчевский редактировал «Справочный энциклопедический словарь» типография К. Крайя (12 томов; первый оконченный словарь на русском языке); в 1850-х годах был вторым редактором «Библиотеки для Чтения» Сенковского.

В 1856 году он преобразовал «Сын Отечества» в дешевую еженедельную газету. Успех её обогатил издателя-редактора, но 13 лет спустя он должен был отказаться от издания газеты. После неудачной попытки возобновить «Северную Пчелу», Старчевский стал редактором «Сына Отечества», приобретенного мучным торговцем Успенским, но, несмотря на громадный труд в течение семи лет, не мог возвратить газете и малой части её прежнего успеха. В 1879—1885 годах Старчевский редактировал ещё «Современность», «Улей», «Эхо» и «Родину».

Довольно обширный отдел его трудов составляют разного рода «Переводчики» с восточных языков, «Спутники», «Толмачи» и тому подобные труды по Средней Азии, Кавказу, Турции, Индии и прочим странам, из которых некоторые выдержали по несколько изданий. Последняя крупная его работа — «Словарь древнего славянского языка, составленный по Остромирову Евангелию, Миклошичу, Востокову и Бередникову» (Санкт-Петербург, 1899). Между журнальными его статьями выделяются:

«Великая мысль Екатерины II» («Исторический Вестник», 1885, № 7);

«Воспоминания старого литератора» («Исторический Вестник», 1888, 10 и 1889, 10);

«Роман одной забытой романистки» («Исторический Вестник», 1886, № 8 и 9);

«Дудышкин Степан Семёнович. Один из забытых журналистов» («Исторический Вестник», 1886, № 2).

А. В.Старчевский скончался 7 октября 1901 года в Санкт-Петербурге. Похоронен на Волковском лютеранском кладбище.