II июля 1896 г. "Наварин" под командованием капитана I ранга П. А. Безобразова, неся флаг командующего отрядом в Средиземном море, надолго покинул Кронштадт. На корабле находились 616 офицеров и матросов 9 флотского экипажа. В погребах и крюйт-камерах броненосца хранились 450 зарядов и 290 снарядов для 305-мм орудий, 1116 зарядов и 1232 снарядов 152-мм орудий и 24160 патронов к 47-и 37-мм пушкам.
Вместе с "Наварином" (командир капитан I ранга П. Безобразов) в Средиземное море уходил и "Император Александр II" (командир капитан I ранга К. Никонов), минный крейсер "Посадник" (командир капитан 2 ранга Р. Вирен) и миноносцы № 119 и № 120 (командиры лейтенанты А. Лебедев и В. Нащинский).
7 августа отряд прибыл в Киль. Затем последовали заходы в Христианзанд, Портленд, и 27-го корабли бросили якорь в Кадиксе. Через неделю они находились уже в Алжире и чуть позже пришли в Пирей. Выйдя 10 сентября из Пирея, "Наварин" на пути в бухту Мерсин на Малоазиатском полуострове произвел пробную стрельбу из всех торпедных аппаратов. Стрельбу оценили как успешную.
Через пять дней при следовании обратно в Пирей броненосец попал в семибалльный шторм. Сила ветра достигала 10-балльной отметки. Огромные волны свободно гуляли на баке и юте. Сильные их удары приходились в порты 152-мм орудий. К счастью, все они были плотно закрыты, и в батарейную палубу протекло незначительное количество воды. Размахи качки при этом достигали до 27° на борт. На "Наварине" сильно пострадали дельные вещи из дерева. Водяными потоками сорвало все 16 крышек из красного дерева со светлых машинных люков. Через них в машину начала проникать вода. Одновременно с мостика снесло ящик с принадлежностями от орудия Готчкисса и выдавило несколько иллюминаторов в кают-компании.
Зайдя в Пирей и простояв там до 13 октября, "Наварин" по приказу командующего отряда ушел в Суду — порт с обширной бухтой на острове Крит. В Судской бухте "Наварин" застал большое скопление кораблей флотов Средиземного региона.
Первым при подходе к якорной стоянке встретили уходивший в море английский броненосец "Hood". Кроме него Англию представляли броненосец "Barfleur" и крейсера "Scout" и "Blanche". У самого входа в бухту стоял французский броненосец "Marceau", а в бухте минный крейсер "Wattignies".
Самым большим был отряд итальянских кораблей. На рейде мирно дымил эскадренный броненосец "Francesco Moposini" под флагом контр-адмирала Гуалтиери, за ним стояли "Ruggiero di Louria" и "Andrea Doria", боевые суда IV класса "Giovani Bausan", "Stromboli", "Vesuvio" и боевое судно V класса "Liguria". Находилась здесь и турецкая эскадра, состоящая из броненосца "Мухадели Хаир", крейсера "Хайбетнума" и канонерской лодки "Искандерие". Став на якорь, "Наварин" произвел салют наций.