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