Так человек, которому судьба отводила в будущем такое блестящее место в немногочисленной плеяде русских кавалерийских вождей, начал свою службу в пехоте, в Менгрельском полку, с которым и выступил в турецкую кампанию 1808 года. С этих пор начинается его боевая известность. Командуя ротой, Мадатов, менее чем в два года, получил Анну и Владимира с бантами, Анну на шею, золотую шпагу за храбрость и чин капитана. Но уроженцу Карабага, страны отважных наездников, пехотная служба представляла мало простора; он рвался в кавалерию, и в феврале 1810 года ему наконец удалось осуществить свою заветную мечту: он был переведен в Александрийский гусарский полк ротмистром. Не успел он еще доехать до полка, как было получено известие о производстве его в майоры за прежние боевые отличия. В настоящее время такие поздние переводы из пехоты в кавалерию показались бы чем-то совсем необычайным: Но тогда подобные случаи бывали нередко. И не один Мадатов, многие знаменитейшие боевые русские кавалеристы вышли именно из рядов пехоты. Проще были тогда специальные требования от кавалерии, ближе стояла она к действительным боевым потребностям, и развитие духа преобладало в ней над технической стороной дела.
И вот пехотный майор, надев гусарский ментик, явился в Александрийский полк, издавна славившийся в сражениях “яростью ударов”, и тотчас получил эскадрон. Полк был в то время на походе к Шумле, и 12 июля, при селении Чаушкиой, произошло первое дело, в котором Мадатову пришлось участвовать с гусарами. Здесь, на глазах своих новых товарищей, врубился он со своим эскадроном в пехотную колонну – и возвратился назад с турецкой пушкой. Первый бой – и уже право на Георгия! Храбрые александрийцы увидели в Мадатове достойного сотоварища, и положение его в полку упрочилось сразу. Нужно сказать, что Александрийским полком командовал в то время полковник Ланской, убитый в 1814 году под Краоном, человек блистательной храбрости, которой завидовал даже сам Мадатов. Однажды, в десятом году, завязалась жаркая битва под Шумлой. Ланской ввел в дело весь Александрийский полк. Гусары шли на рысях; Мадатов видел, как Ланской ехал перед первым эскадроном, окруженный своим конвоем, в числе которого был юнкер Новинский. Полк уже близко подошел к турецкому ретраншементу, когда Ланской скомандовал: “Марш-марш”. Он первый вскочил в укрепление, и, вырвав из рук турецкого байрактара знамя, бросил его Новинскому, крикнул: “Юнкер! Вот тебе георгиевский крест!”
Такая беззаветная отвага воодушевила всех александрийцев, и нелегко было состязаться с ними в храбрости. Но Мадатов жадно искал случая выделиться из среды даже таких сотоварищей,– и случай к этому не замедлил представиться.