I июня 1896 г., когда подготовка к дальнему плаванию "Наварина" и "Гангута" шла полным ходом главный командир Кронштадтского порта предложил в поход назначить (взамен "Гангута") броненосец "Император Александр II" который, по его словам, "не только находится в лучших условиях боевой готовности, но даже может быть изготовлен в сравнительно меньший срок".
II июля 1896 г. "Наварин" под командованием капитана I ранга П. А. Безобразова, неся флаг командующего отрядом в Средиземном море, надолго покинул Кронштадт. На корабле находились 616 офицеров и матросов 9 флотского экипажа. В погребах и крюйт-камерах броненосца хранились 450 зарядов и 290 снарядов для 305-мм орудий, 1116 зарядов и 1232 снарядов 152-мм орудий и 24160 патронов к 47-и 37-мм пушкам.
Вместе с "Наварином" {командир капитан I ранга П. Безобразов) в Средиземное море уходил и "Император Александр II" (командир капитан I ранга К. Никонов), минный крейсер "Посадник" (командир капитан 2 ранга Р. Вирен) и миноносцы № П9 и № 120 командиры лейтенанты А. Лебедев и В. Нащинский).
7 августа отряд прибыл в Киль. Затем последовали заходы в Христиапзанд, Портленд, и 27-го корабли бросили якорь в Кадиксе. Через педелю они находились уже в Алжире и чуть позже пришли в Пирей.
Выйдя 10 сентября из Пирея, "Наварин" на пути в бухту Мерсин на Малоазиатском полуострове произвел пробную стрельбу из всех торпедных аппаратов. Стрельбу оценили как успешную.
Через пять дней при следовании обратно в Пирей броненосец попал в семибалльный шторм. Сила ветра достигала 10-балльной отметки. Огромные волны свободно гуляли на баке и юте. Сильные их удары приходились в порты 152-мм орудий. К счастью, все они были плотно закрыты, и в батарейную палубу протекло незначительное количество воды. Размахи качки при этом достигали до 27° на борт На "Наварине" сильно пострадали дельные вещи из дерева. Водяными потоками сорвало все 16 крышек из красного дерева со светлых машинных люков. Через них в машину начала проникать вода. Одновременно с мостика снесло ящик с принадлежностями от орудия Готчкисса и выдавило несколько иллюминаторов в кают-компании.
Зайдя в Пирей и простояв там до 13 октября, "Наварин" по приказу командующего отряда ушел в Суду – порт с обширной бухтой на острове Крит. В Судской бухте "Наварин" застал большое скопление кораблей флотов Средиземного региона.
Первым при подходе к якорной стоянке встретили уходивший в море английский броненосец "Hood". Кроме него Англию представляли броненосец "Barfleur" и крейсера "Scout" и "Blanche". У самого входа в бухту стоял французский броненосец "Marceau", а в бухте минный крейсер "Wattigmes".
Самым большим был отряд итальянских кораблей. На рейде мирно дымил эскадренный броненосец " Frаncesсо Moposini" под флагом контр-адмирала Гуалтиери, за ним стояли "Ruggiero di Louria" и "Andria Doria", боевые суда IV класса "Giovani Bausan", "Stromboli", "Vesuvio" и боевое судно V класса "Liguria" Находилась здесь и турецкая эскадра, состоящая из броненосца "Мухадели Хаир", крейсера "Хамбегнума" и канонерской лодки "Искандерие". Слав на якорь. "Наварин" произвел салют наций.
На переходе в Суду заметно сказалось обрастание водорослями подводной части. Теплый климат Средиземноморья этому весьма способствовал. Идя при 65 оборотах винта, что соответствовало скорости в 12 уз., "Наварин" фактически едва давал 11.2 узла.
Заменив в Суде нашего стационара – канонерскую лодку "Грозящий", броненосец простоял там до 3 ноября.
Во время этой стоянки однажды выходили на стрельбы. Сначала стреляли малокалиберном артиллерией, а затем из 152-мм орудии. Особенно удачной оказалась вторая стрельба. Сделав всего шесть выстрелов, комендоры, умело управляя огнем, полностью разбили щит. Стрельбу пришлось окончить.
Из Суды корабль ушел в Смирну. Придя туда 6 ноября, "Наварин" застал корабли Североамериканских Соединенных штатов под командой контр-адмирала Сельфриджа, державшего свой флаг на крейсере "San Francisco". В его отряде находились крейсера "Minneapolis" и "Cincinnati". В бухте стоял и нидерландский отряд: фрегат "Prise" и авизо "Seehond".
Простояв в Смирне до 12 декабря, "Наварин" убыл в Пирей, где встретился с канонерской лодкой "Запорожец". Сделав затем в Пи рее однодневный выход, провели торпедные стрельбы. Сначала стреляли для согласования прицелов в веху, отстоявшую на 300 м от корабля. Затем, подняв откидными стрелами па борт торпеды, перезарядив аппараты, уже па ходу произвели по вехе новый залп.
Новый 1897 г. "Наварин" встретил у берегов Греции у о. Порос. В начале 1897 г. на Крите произошли межэтнические столкновения. Греческая и турецкая общины, враждебные между собой, вступили в открытый конфликт, повлекший за собой многочисленные человеческие жертвы. В конфликт постепенно начали вмешиваться и правительства Греции и Турции. Назревала воина. Греция, не согласная с решением коалиции ведущих стран: Англии, Франции, России, Италии и Германии о блокаде Крита, вступила на путь обострения отношении с ними.