Одновременно со штурмом Эрзерума 4-й Кавказский корпус генерал-лейтенанта В.В. де Витта проводил вспомогательную операцию, захватив города Муш и Битлис, причем в плен попали 59 вражеских офицеров и 1427 солдат. Эти бои плавно перетекли в следующую операцию, которой руководил Юденич, — Трапезундскую. Через черноморский порт Трапезунд шло снабжение всех турецких войск на кавказском театре военных действий, через него же могли быть быстро переброшены на Кавказ свежие вражеские силы с Галлиполийского полуострова. Конечно, по чести говоря, задачу ликвидации Трапезундской базы мог бы взять на себя Черноморский флот, однако к началу 1916-го он так и не смог полностью взять под свой контроль морские коммуникации.
Трапезундской операцией руководил лично Н.Н. Юденич, находившийся на борту транспорта «Великий князь Александр Михайлович». Благодаря мужеству бойцов небольшого Приморского отряда, командиром которого был временно назначен комендант Михайловской крепости генерал-майор Владимир Платонович Ляхов, и десантников Кубанских пластунских бригад сильно укрепленный рубеж обороны противника на левом берегу реки Кара-Дере был взят быстро и без больших потерь. Особенно отличился 19-й Туркестанский стрелковый полк (командир — полковник Борис Нилович Литвинов), который форсировал Кара-Дере под убийственным огнем противника. Мост через реку турки взорвали как раз в тот момент, когда его пересекали бойцы 6-й роты. Но это не помешало остаткам доблестной роты выбраться на берег и могучим ударом выбить ошеломленного врага с позиций… 5 апреля Трапезунд пал.
Турецкое население бежало из города, а греческое и армянское радостно вышло приветствовать своих освободителей. Офицеров и солдат забрасывали цветами. Н.Н. Юденич в сопровождении чинов своего штаба пешком направился в старинный собор Святой Софии, где был отслужен молебен о здравии императора России и о даровании окончательной победы русским войскам, а затем принял делегацию почетных граждан города.
Невзирая на тяжелейшее поражение, которое турецкие вооруженные силы потерпели под Эрзерумом, они чрезвычайно быстро, уже в мае 1916 года, начали предпринимать попытки вернуть утраченные на Кавказе позиции. В третий раз была возрождена из небытия 3-я армия, по железной дороге на Эрзерумское направление была переброшена сильная 2-я армия, воодушевленная недавними победами над англичанами. Военачальники Османской империи прекрасно осознавали стратегическую важность Эрзерумского района и порта Трапезунд и были полны решимости как минимум отбросить войска Юденича на исходные позиции, как максимум — выбить их за пределы государственной границы Турции и уничтожить.
На рассвете 16 мая турки обрушились на позиции 15-го Кавказского стрелкового полка, сломили его сопротивление и двинулись на Эрзерум. Но дорогу врагу перекрыли закаленные сражениями полки 39-й пехотной дивизии. На протяжении трех дней, с 21 по 23 мая, 153-й пехотный Бакинский полк, которым с 7 апреля командовал полковник Е.В. Масловский, один держался против четырех вражеских дивизий, отразив две кавалерийские атаки и потеряв убитыми и ранеными 15 офицеров и более 900 нижних чинов.
13 июня два корпуса 3-й турецкой армии начали мощное наступление на Трапезундском направлении. Положение здесь спасли герои Трапезунда — стрелки 19-го Туркестанского полка, который в течение двух суток сражался с двумя дивизиями. В этом беспримерном бою только убитыми турки потеряли 6 тысяч человек, но и потери 19-го Туркестанского были огромны: из 60 офицеров погибли 43, а из 3200 солдат — 2069. Оборона переросла в наступление: 1-й Кавказский корпус отбросил 9-й и 11-й турецкие корпуса, а 2-й Туркестанский корпус вел бои с 10-м турецким. 2 июля русскими войсками был взят город Байбурт, 10-го — город Эрзинджан. 3-я турецкая армия была разгромлена Отдельной Кавказской уже в третий раз подряд, в плен попали около 17 тысяч вражеских офицеров и солдат, было взято около 20 орудий и 50 пулеметов.