Вскоре началась война с Турцией. По общему плану военных действий Паскевич для отвлечения сил турок от главного театра войны на Балканском полуострове должен был напасть на азиатские их владения. Лично командуя войсками, он выступил 14 июня 1828 г. из Гумров к Карсу, под стенами его разбил турецкую кавалерию и затем, осадив эту крепость (цитадель), принудил ее сдаться. После штурма в войсках началась чума, прекращенная быстрыми и энергичными распоряжениями Паскевича, который, совершив трудный переход чрез высокий Чатырдагский хребет, подошел к крепости Ахалкалаки и взял ее штурмом 23 июля, после чего сдалась и близлежащая крепость Хертвис. Тем временем другим отрядом войск была взята крепость Поти. Паскевич, удостоенный лестного рескрипта государя и назначенный шефом Ширванского пехотного полка, двинулся от Ахалкалаки к крепости Ахалцых и, разбив многочисленную турецкую кавалерию, пришедшую ей на помощь, начал ее осаду. В это время подошла турецкая армия в 30 000 человек и стала в укрепленной позиции в трех верстах от города. После упорного сражения, продолжавшегося целый день, 9 августа эта армию турок разбили, а затем 15 августа начали штурм Ахалцыха, который сдался. Паскевича наградили орденом Св. Андрея Первозванного, а Ширванский пехотный полк назвали его именем. Пользуясь ужасом, наведенным на турок, Паскевич занял крепости Ацхур, Ардаган, Баязет и Диадин и направил часть войска для отдыха в Грузию. Назначенный новый турецкий главнокомандующий Салех-Паша Мандайский в феврале 1829 г. решился отнять Ахалцых, а потому, обложив его, неоднократно штурмовал эту крепость. Паскевич послал Бурцова и Муравьева с отрядами освободить Ахалцых, что и было ими исполнено, а сам, ввиду значительных приготовлений турок к новой кампании, стал между Карсом и Ардаганом, чтобы действовать по усмотрению прямо на Эрзерум. Турки же сосредоточивались на Саганлугском хребте, через который идет дорога из Карса в Эрзерум. После незначительных стычек 20 июля Паскевич овладел лагерем турок и совершенно рассеял их войска, 25 июля подошел к Эрзеруму – столице Анатолии, и потребовал ее сдачи. Несогласие на это турок заставило Паскевича овладеть укрепленной высотой Топ-Даг, после чего Эрзерум сдался. Паскевич, только что награжденный алмазными знаками ордена Св. Андрея Первозванного за поражение турок, за покорение Эрзерума был пожалован орденом Св. Георгия I степени.
Тем временем горные племена лазов покусились вытеснить наши войска из крепости Байбурта. Паскевич лично двинулся против них и рассеял их совершенно. После этого он делал небольшие экспедиции в разные стороны от Эрзерума для изгнания неприятельских отрядов. В день заключения Андрианопольского мира (22 сентября 1829 г.) на пожалованного в звание генерал-фельдмаршала Паскевича высочайше возложили покорение горских народов, населявших Кавказские горы.
Он начал действия против лезгин в 1830 г., принудил их дать присягу на подданство и заложил крепость при Закатальском ущелье. Направившись затем на северную сторону Кавказа, он постепенно теснил горцев за Кубанью, возводил укрепления в земле шапсугов и абазехов, овладел тесниной Гагры, занял Соук-су и Пицундскую бухту, а затем переправился на левый берег Кубани, ниже Екатеринодара, где рассеял шапсугов.
Паскевич обращал особенное внимание на нужды края и на благосостояние жителей; он заботился о приведении в известность казенного имущества всякого рода, исправлении всех укреплений, искоренении по возможности всех вопиющих злоупотреблений в сферах суда и администрации в этом отдаленном крае. Он составил положение об управлении армяно-грегорианской церковью, о преобразовании благородного училища в Тифлисе в гимназию. По его представлению там же учреждены Институт благородных девиц, Тифлисская публичная библиотека и газета «Тифлисские ведомости». В его же управление окончательно присоединена к Российской империи в 1828 г. Гурия. Климат Кавказа неблагоприятно влиял на здоровье Паскевича, в конце 1830 г. он занемог и просил государя вызвать его с Кавказа.
Но в Варшаве 17 ноября 1830 г. вспыхнуло восстание, быстро распространившееся по всему королевству. Для усмирения его направили войска под начальством фельдмаршала графа Дибича, который оттеснил мятежников к Висле, но после сражения при Грохове и Остроленке он умер от холеры.
Заменить его приказали Паскевичу. Желая избегнуть кровопролития, Паскевич предложил полякам условия сдачи, которые были ими отвергнуты. Последствием этого 25 августа стал штурм предместья Варшавы – укрепленного селения Воля, взятого после отчаянного сопротивления в 11 часов утра. Мятежники вступили в переговоры, но не хотели согласиться на безусловную сдачу города. Поэтому Паскевич прекратил переговоры и приступил немедленно к штурму города Варшавы. Началось жестокое сражение, в котором Паскевич получил сильную контузию ядром в левую руку.