Андрей Марков страдал туберкулёзом коленного сустава и до 10 лет ходил на костылях. После операции, проведённой известным хирургом Кадэ, он получил возможность ходить нормально.

В 1866 году его отдали в 5-ю Петербургскую гимназию. Это классическое учебное заведение с преподаванием древних языков (латинского и греческого) пришлось ему не по вкусу; по большинству предметов он учился плохо, исключение составлял только один предмет — математика.

В 1874 году А. А. Марков окончил гимназию и поступил в Санкт-Петербургский университет. Там он слушал лекции профессоров А. Н. Коркина и Е. И. Золотарёва, а также Пафнутия Львовича Чебышёва, оказавшего определяющее влияние на выбор научной деятельности Андрея Маркова. 31 мая 1878 года он окончил Петербургский университет по математическому разряду физико-математического факультета со степенью кандидата. В том же году он был награждён золотой медалью за сочинение «Об интегрировании дифференциальных уравнений при помощи непрерывных дробей» и был оставлен при Университете «для приготовления к профессорскому званию». В 1880 году он защитил свою знаменитую магистерскую диссертацию, сразу выдвинувшую его в первые ряды русских математиков, а через год – докторскую диссертацию.

Его преподавательская деятельность в Петербургском университете началась в 1880 году в качестве приват-доцента. В 1883 году начал читать курс «Введение в анализ», а затем – курс теории вероятностей.

В 1883 году А. А. Марков женился на Марии Ивановне Вальватьевой. Через 20 лет у них родился сын Андрей (полный тёзка отца и также математик).

С 2 марта 1896 года — ординарный академик Императорской Санкт-Петербургской академии наук.

Умер в Петрограде в 1922 году.