Война за независимость Германии дала Малахову случаи к новым блестящим отличиям. Первая встреча с французами за рубежом русской земли произошла у него под Калишем, 1 февраля 1813 года. Малахову, с двумя эскадронами гусар, удалось разбить здесь сильную французскую конницу. Но в эту минуту, когда неприятель дал перед ним тыл, показались два саксонские батальона, которые шли, свернувшись в густую колонну. В пылу одушевления, Малахов тотчас повернул на них; но неприятель был силен и, остановившись, спокойно выжидал атаки. Малахов понял, что сломить такую пехоту трудно. Но военное счастье редко изменяет истинной отваге. Он стал впереди гусар и сам, во главе дивизиона, кинулся на неприятеля... Залп, ответный крик на него: “Ура!” – и гусары врубились в пехоту. Две пушки и саксонское знамя захвачены были с первого удара. Пехота, разорванная в рядах, дралась, однако, штыками, но, смятая и стоптанная, бросила наконец оружие. Два батальона и командовавший ими генерал граф Ностиц были взяты в плен. Малахов получил за этот блестящий подвиг орден св. Георгия 3-ей степени и, таким образом, был одним из весьма немногих офицеров в русской армии, имевших в чине полковника и бриллиантовую саблю, и Георгия на шее.

Затем Мадатов с отдельным отрядом блокировал крепость Глогау, сражался под Люценом, участвовал в нескольких отважных партизанских поисках и был в битве народов под Лейпцигом. Здесь, в пылу одной из атак Александрийского полка, он был жестоко ранен пулей в левую руку, но не сошел с коня и не оставил поля до окончания битвы. Это крайнее напряжение воли дорого стоило Малахову: сильная потеря крови и несвоевременная перевязка настолько ухудшили состояние раны, что болезнь надолго приковала Мадатова к постели. Это было причиной, что он не мог участвовать в кампании 1814 года. Но Мадатов не был забыт: государь пожаловал ему чин генерал-майора и орден Владимира 3-ей степени, а прусский король прислал ему орден.

Посетив Париж уже по заключении мира, Мадатов хлопотал о переводе его в корпус графа Воронцова, оставляемый во Франции. Но в это время уже состоялся приказ о назначении его на службу в отдельный Грузинский корпус. И вот Мадатов, за шестнадцать лет перед тем покинувший родину бедным, никому не нужным сиротой, теперь возвратился в нее правителем трех мусульманских ханств: Ширванского, Шекинского и Карабагского.

С этого момента начинается славная боевая деятельность Мадатова на Кавказе, навеки связавшая имя его с целым рядом выдающихся событий кавказской войны. Войска, предводимые им, проникали в такие места, в которых еще никогда не бывала нога победителей, и где народ не знал, что значит быть побежденным. Его видели в своих стенах неприступные аулы Лаваши и Хозрек; горы Дагестана склоняли перед ним свои непокоренные головы, а Шамхорское поле дало его имени неувядаемый блеск. Ермолов высоко ценил победы Мадатова, но еще выше ставил нравственное влияние, которое он приобретал над побежденными народами и которое было так сильно, что заставляло недавних врагов становиться под знамена Мадатова и идти на бой со своими единоземцами. Так было в Каракайтаге, в Табасарани и Казикумыке, так было и во время персидской войны, в Казахской дистанции. Скупой на награды, Ермолов не жалел их для Мадатова: за Табасарань и Башлы он получил анненскую ленту, за Акушу – алмазные знаки Анны 1-ой степени, за Казикумык – Владимира 2-го класса, за Шамхор и Елизаветполь – чин генерал-лейтенанта и вторую бриллиантовую саблю.

Не все, конечно, подобно Ермолову, умели ценить эту энергичную и плодотворную деятельность Мадатова. На самую память его брошено несколько жестких обвинений, в которых ему не пришлось найти всеобщего оправдания, хотя, конечно, и были люди, лучше понимавшие его и его положение. Следя за его управлением татарскими провинциями, многие и при жизни его и после находили в его действиях нечто азиатское, произвольное и деспотичное, от чего будто бы он сам, уроженец Азии, воспринявший с детства все политические и общественные понятия ее, не мог отрешиться в течение всей своей жизни. Что в его действиях был этот характер,– оспаривать никто не будет; но ему есть другое, более веское и логическое объяснение. Нужно представить себе этот край, в котором ничто не уважается, кроме силы и власти, край, только что перешедший из рук ханского произвола под господство закона и не утративший ни одной черты в понятиях, которыми объяснялась и поддерживалась деспотичная власть, чтобы понять, что Мадатов, коротко его знавший, только приноравливался к его обычаям и нравам. Так, чтобы вызвать необходимое обаяние своей власти, он, как рассказывают, донося о всех предположенных им смертных приговорах, вместе с тем всегда представлял народу дело в таком свете, что он своей властью казнит и имеет на то право; и это было целесообразно с нравами и понятиями мусульман. Не нужно, притом, забывать и другой стороны деятельности его, той, что знание края давало ему постоянную возможность исправлять ошибки других. “Справедливость,– говорит один из современников Мадатова, бывший вместе с ним позже в Турции,– может быть достигнута только сравнением того, что совершил князь, с тем, чего не сделали или что испортили другие... Грузия была свидетельницей того же, что происходило на моих глазах в Турции. Делались огромные ошибки; князь исправлял их, и в то время, когда им уже были сорваны лавры, являлись распоряжения, мешавшие ему доплести из них венок...”

Падение Ермолова увлекло за собой и его любимого сподвижника. Мадатов сошел со сцены кавказской войны не обиженным только, но глубоко и несправедливо оскорбленным. Имение в Карабаге, оставленное за ним высочайшей волей не без политических расчетов, послужило для Паскевича главным предлогом к его обвинению и создало нарекания, мрачной тенью отразившиеся не только на нем, но и на самом Ермолове,– честность которого уже отмечена историей.

В тягостном и непривычном бездействии пробыл Мадатов в Тифлисе целые пять месяцев. Наконец, через Дибича ему удалось добиться позволения приехать в Петербург. В то время шли уже приготовления к турецкой войне, и Мадатов был прикомандирован к третьему пехотному корпусу, входившему в состав действующей армии. Там, на Дунае, с небольшим отрядом он овладел двумя турецкими крепостями, Исакчей и Гирсовым, и отстоял селение Проводы, расположенное у подошвы Балкан. “Ура! Любезный князь,– писал ему граф Воронцов из-под Варны,– я знал, что герой Дагестана будет героем и в Балканских горах”. Четырнадцать знамен и девяносто восемь орудий были трофеями Мадатова в эту кампанию. И несмотря на все это, неблаговоление Паскевича так сильно отражалось на службе его, что Мадатов за весь этот поход получил только одно “монаршее благоволение”. Наконец, уже в начале 1829 года, он был назначен начальником третьей гусарской дивизии. И вот, на тех самых полях, на которых за двадцать лет перед тем Мадатов получил георгиевский крест, теперь пришлось ему встретиться опять с александрийцами, уже входившими в состав его дивизии. “Ну, слава Богу,– шутил он с гусарами,– мы опять увидим турок. Только вы, братцы, их всех не рубите; за пленных дают по червонцу – сгодится, а лошадей их мы маркитантам за долг отдадим”. И гусары восторженно глядели на того, чье имя давно уже тесно связалось с их полковой славой.

В это. время имя Мадатова почти не упоминалось в реляциях, но популярность его в армии была велика. Вот как описывает, между прочим, один артиллерийский офицер свою встречу с ним в кампанию 1823 года, около Пазарджика.