Born to a noble family in the Moscow Guberniya, Markov enlisted as a private in the Perm Infantry Regiment on 16 December 1770, and was made ensign on 29 November 1772.

On 29 June 1788, he was promoted to second major, and participated in the Russo-Turkish War, serving under Alexander Suvorov commanding the 2nd line at Kinburn 13 October.

He was awarded a golden cross and the Order of St. George (4th class) during the Siege of Ochakov on 11 April 1792, where he was wounded in the head.

After recovery he was made a premier major in the Apsheron Infantry Regiment in 1792, serving in the Polish campaigns of 1792-1794 (see Polish–Russian War of 1792 and Kościuszko Uprising) and seeing action at Gorodische, Dubienka, and Praga.

Then he served under Chichagov, but was dismissed for incompetence, when it was found that despite his high-rank, his strategising characterised by such basic errors as confusing roads with rivers on maps.