А. А. Марков был сыном чиновника Андрея Григорьевича Маркова, служившего в Лесном департаменте в чине коллежского советника, а затем вышедшего в отставку и служившего в Санкт-Петербурге частным поверенным и управляющим имением Екатерины Александровны Вальватьевой. Отец Андрея Григорьевича, Григорий Маркович Марков, был сельским дьяконом. Андрей Григорьевич был дважды женат; от первой жены, дочери чиновника, Надежды Петровны Фёдоровой, он имел шестерых детей: Петра, Павла (умершего в детстве), Марию, Евгению, Андрея и Михаила; от второй жены, Анны Иосифовны, — трёх: Владимира, Лидию и Екатерину. Владимир Андреевич (1871—1897) показал себя первоклассным математиком, но рано умер от туберкулёза. Сестра отца, врач-психиатр Евгения Андреевна (?—1920), была одной из первых русских женщин-врачей. Андрей Марков страдал туберкулёзом коленного сустава и до 10 лет ходил на костылях. После операции, проведённой известным хирургом Кадэ, он получил возможность ходить нормально. В 1866 году его отдали в 5-ю Петербургскую гимназию. Это классическое учебное заведение с преподаванием древних языков (латинского и греческого) пришлось ему не по вкусу; по большинству предметов он учился плохо, исключение составлял только один предмет — математика. В 1874 году А. А. Марков окончил гимназию и поступил в Санкт-Петербургский университет. Там он слушал лекции профессоров А. Н. Коркина и Е. И. Золотарёва, а также Пафнутия Львовича Чебышёва, оказавшего определяющее влияние на выбор научной деятельности Андрея Маркова. 31 мая 1878 года он окончил Петербургский университет по математическому разряду физико-математического факультета со степенью кандидата. В том же году он был награждён золотой медалью за сочинение «Об интегрировании дифференциальных уравнений при помощи непрерывных дробей» и был оставлен при Университете «для приготовления к профессорскому званию». В 1880 году он защитил свою знаменитую магистерскую диссертацию «О бинарных квадратичных формах положительного определителя», сразу выдвинувшую его в первые ряды русских математиков. В 1881 году состоялась защита докторской диссертации «О некоторых приложениях алгебраических непрерывных дробей». Его преподавательская деятельность в Петербургском университете началась в 1880 году в качестве приват-доцента. В 1883 году ему был передан курс «Введения в анализ», до того читавшийся Ю. В. Сохоцким и К. А. Поссе. В этом же году университет покинул Чебышёв, и Марков впервые прочитал курс теории вероятностей. В 1883 году А. А. Марков женился на Марии Ивановне Вальватьевой. Через 20 лет у них родился сын Андрей (полный тёзка отца). С 13 декабря 1886 года, по предложению Чебышёва, он был избран адъюнктом физико-математического отделения (чистая математика); с 3 марта 1890 года — экстраординарный академик, а с 2 марта 1896 года — ординарный академик Императорской Санкт-Петербургской академии наук. С 1880 года — приват-доцент, с 1886 года — профессор физико-математического факультета Санкт-Петербургского университета. С 1898 года — действительный статский советник.
