В арзерумском походе, помимо русских солдат, участвовали четыре конно-мусульманских полка, грузинские «татары», во главе со своими беками и агаларами (представители мусульманского населения Грузии), армяне Эриванской области из числа бывших персидских солдат-сарбазов, и курдские отряды. Армянская конница действовала также хорошо как и мусульманская, но пехота, на взгляд русского командования, выглядела потешно. То, что русские солдаты несли на себе (провиант, амуницию и т. д), армянские пехотинцы по персидскому обычаю везли отдельно, используя гужевой транспорт. Среди ополченцев были нередки случаи самовольного ухода домой, когда воин начинал вдруг скучать по маме или девушке.
Первым успехом российских войск в Арзерумском походе можно считать переход через Саганлугский хребет. Здесь херсонский полк Бурцова отвлек на себя главные турецкие силы и Кавказский корпус преодолел горные высоты без боя.
Пушкин был свидетелем того, как на реке Инджа-Су турецкий отряд в 500 человек пытался разгромить русские аванпосты. Замечено было Пушкиным и то, что турки обезглавливают трупы русских солдат — головы отсылались в Константинополь, видимо для поднятия настроения у султана и столичной толпы.
16 июня состоялась сражение с турецким авангардом, под командованием Осман-паши Бордуса. Конно-мусульманские части показали себя с наилучшей стороны.
19 июня при Каинлы был разгромлен 30-тысячный корпус сераскира Гаджи-Салеха, сам он попал в плен. Здесь в очередной раз отличился херсонский полк Бурцова, отразивший бешенный натиск турецкой конницы.
Затем у Милли-Дюза был разбит корпус Гагки-паши, его командующий взят в плен казаками. И вновь конно-мусульманские полки были на высоте. Однако Паскевич, всегда требовавший напряжения сил при преследовании разбитого противника, был недоволен нерешительными действиями генерал-майора Остен-Сакена и отстранил его от командования.
Турецкая крепость Гассан-Кале, которую Пушкин называет «ключом Арзеруму», досталась Паскевичу без боя 24 июня.
Взятие Арзерума оказалось не слишком тяжелой задачей. Отпущенные Паскевичем пленные турки сообщили жителям города, что не сераскир разбил русских, а совсем наоборот. Удивление оказалось столь велико, что в Арзеруме начались волнения. Турецкие солдаты, расстроенные потерей народной любви, бросили защищенные артиллерией позиции на высоте Топ-дага, на восточной стороне города. Русский парламентер Бекович-Черкасский (внук князя Бековича, погибшего при Петре в первом хивинском походе) принудил город и сераскира к сдаче. Очевидно, после недавних поражений у турок просто не было сил, чтобы защищать Арзерум. 27 июня (9 июля) войска Паскевича вошли в столицу азиатской Турции, имевшую стотысячное население. Для них теперь открывался путь к Трапезунду.
В противоположность тем сценам насилия, которые творились в городах, занятых турками и персами, в покоренном русскими Арзеруме было тихо. Не тронуты были и гаремы пашей, воевавших против России. Как писал Пушкин, в Арзеруме, где находилось 10 тыс. русского войска, «ни один из жителей ни разу не пожаловался на насилие солдата».
В своем письме Паскевичу император сказал: «Трудно мне выразить, любезный мой Иван Федорович, с каким душевным удовольствием получил я известия, привезенные Дадиановым и Фелькерзамом. Вы все сделали, что можно только ждать после продолжительной и трудной кампании и все сделали в 14 дней; вы вновь прославили имя русское, храброе наше войско и сами приобрели новую, неувядаемую славу; да будет награда вам — первая степень Георгия — памятником для вас и для войск, вами предводительствуемых, славных ваших подвигов и того уважения, которое с искренней дружбой и благодарностью моей навеки принадлежит вам. Изъявите всем мое совершенное удовольствие и признательность;
20 июня, турецкое войско, двигавшиееся из Вана, подошло к Баязету, где стоял русский гарнизон. Туркам удалось занять часть города, но на следующий день они были выбиты русскими из всех кварталов, а армянское ополчение произвело «зачистку».
Подразделения херсонского полка, возглавляемые Бурцовым, занимают укрепленный Бейбурт, главный город лазов. После этого Бурцов пытается взять лазское селение Харт, находящееся на пути в Трапезунд.
Отряд майора Засса не успел подойти к нему на помощь и несколько сотен херсонцев увязли в уличных боях. После подхода дополнительных турецких сил, Бурцов со своими солдатами вынужден был отступить. Армянская конница на этот раз оказалась не на высоте, и не смогла прикрыть отступление русских сил.