A szentpétervári egyetemen tanult, Csebisev tanítványa volt, majd ő maga is itt tanított, 1893-tól kezdve, mint professzor. 1908-ban politikai okok miatt eltiltották az oktatástól. 1917-től a forradalom idején egy ideig középiskolában tanított, később tért vissza a szentpétervári egyetemre és oktatott ismét 1922-ben bekövetkezett haláláig. A matematika számos területén, így a számelméletben és analízisben is dolgozott, de legfontosabb eredményeit a valószínűségszámítás területén érte el. Bebizonyította a centrális határeloszlástételt. 1906-ban bevezette a Markov-láncok fogalmát, amely alapvető jelentőségre tett szert a sztochasztikus folyamatok elméletében. Számos további fogalom és tétel fűződik a nevéhez, így a Markov-folyamat, Markov-szám, Markov-sorozat. 1890-ban az Orosz Tudományos Akadémia rendkívüli, majd 1896-ban rendes tagjává választották. Fia, akit szintén Andrej Andrejevics Markovnak hívtak (1903-1979), ugyancsak nevezetes matematikus volt.