Побыв короткое время на посту киевского, а затем подольского генерал-губернатора, Гудович в 1799 г. назначается командующим армией для похода на Рейн. Однако скрестить свою шпагу с Наполеоном ему не пришлось. Герой Килии и Анапы совершенно не скрывал своего крайне критического отношения к военным реформам императора, сводившимся к бездумному насаждению прусских образцов, и за это Павел I увольняет прославленного полководца с военной службы.
Но после дворцового переворота 1801 г. новый самодержец вновь призывает Гудовича на военную службу, и в 1806 г. он назначает командующим войсками в Грузии и Дагестане. Старый генерал успешно руководил войсками в действиях против Дербентского, Шекинского и Бакинского ханств, благодаря чему их территории вскоре вошли в состав империи. При этом русские войска не понесли практически никаких потерь, о чем Гудович с гордостью доносил Александру I: «Имею счастье донести Вашему Величеству, что теперь весь Дагестан по реке Кура покорен высокой державе Вашей… Наипаче счастлив я тем, что высочайшая человеколюбивая воля Ваша исполнена не только без потеряния победоносных войск Вашего Величества, но и без малейшего оных изнурения».
Одновременно с завоеваниями для империи новых земель Гудович делал все возможное, чтобы сделать безопасной жизнь мирного населения Кавказа. Как он заявил после вступления в должность: «Будучи старшим генералом русской армии, я недаром прислан сюда водворить между вами порядок». В первую очередь командующий делал все возможное, чтобы интегрировать в имперскую структуру представителей местных элит, и для этого не скупился на чины и звания даже недавним противникам. Например, Гудович пожаловал высокие воинские звания влиятельным дагестанским властителям – уцмию каракайтагскому генерал-майора, а табарасанскому кадию бригадира. Объясняя свои действия, он приводил следующую аргументацию: «Ибо признаю их людьми нужными. Первого – потому что он знатный и сильный владелец, а второго – по смежности его владений с Дербентом».
Подобная политика привлечения на свою сторону бывших врагов полностью себя оправдала, превратив их в преданных союзников.
Не менее удачно действовал Гудович и в начавшейся в 1807 г. войне с Турцией, хотя первоначально его постигла серьезная неудача. Речь идет об осаде сильно укрепленной и имевшей многочисленную артиллерию крепости Ахалкалаки. Гудович рассчитывал, что турки, ввиду значительного превосходства русских сил, сдадутся без боя, и дважды выдвинул требование о капитуляции. В третий раз он направил командовавшему гарнизоном паше следующее требование: «В последний раз советую вам и требую, чтобы вы сдали мне крепость не медля, иначе вас ожидает неминуемая гибель. Представлю в пример то, что многие турецкие крепости с их многочисленными гарнизонами и артиллерией не могли устоять против высокославных российских войск, коими я тогда начальствовал и теперь командую. Я взял их штурмом, где от одного упорства кровь ваших собратьев пролита реками. Анапа, Суджук-Кале и Хаджи-Бей примерные тому свидетели. Показав вам то, что воевать я умею, я еще раз обращаюсь к вашему человеколюбию и уверяю вас моим словом, что в случае вашей покорности вы будете отпущены, а гарнизон получит пощаду».
Однако паша небезосновательно рассчитывал, что без длительной осады русские не смогут преодолеть мощные крепостные укрепления и отказался капитулировать. После этого Гудович начал артиллерийский обстрел, который продолжался два дня. Однако, учитывая отсутствие у русских войск тяжелой осадной артиллерии, а также силу укреплений Ахалкалаки, обстрел принес лишь ограниченный результат, и Гудовичу пришлось начать штурм.
Войска были разделены на три штурмовых колонны под командованием генерал-майоров Титова, Портнягина и Андрея Гудовича (сына командующего), и рано утром 9 мая начался штурм. Турки встретили наступавших концентрированным ружейным и артиллерийским огнем, в результате которого русские войска понесли огромные потери. Только колонна Портнягина сумела взойти на стену, но, несмотря на то, что Гудович направил для ее поддержки все имевшиеся резервы, оборонявшиеся сумели отбить штурм.
Паша попытался развить достигнутый успех и направил из крепости кавалерию для преследования и разгрома русских войск. Но Гудович провел контратаку силами трех эскадронов нарвских драгун и казачьим полком, и турки были вынуждены прекратить преследование.
После того как Гудович отступил от Ахалкалаки в Грузию, турки решили развить свой успех и выступили из Карса к крепости Гумри на реке Арпачай. 20-тысячное турецкое войско (артиллерия которого составляла 25 орудий) было значительно сильнее всех русских сил в регионе, и его командующий эрзерумский сераскир Юсуф-паша надеялся, используя свое численное преимущество, захватить большую часть Кавказа.