Окончание постройки "Наварина" совпала, по времени, с необходимостью немедленного усиления эскадры Средиземного моря, созданной согласно решения Особого совещания 1895 года и резолюции императора Николая II. Соединение российских кораблей в этом районе представляло собой резерв, предназначенный к посылке на Дальний Восток в случае возникновения угрозы войны с Японией. Кроме того, сложный клубок проблем, возникший в связи с обострением греко-турецких отношений, затрагивал интересы многих европейских держав.. Англия, Франция, Германия, Италия направили корабли своих военно-морских флотов в восточную часть Средиземного и Эгейского морей. Россия, естественно, не могла оставаться безучастным зрителем и Главный морской штаб (ГМШ) принял решение направить в Средиземное море два броненосца, преследуя две цели: поддержать престиж империи у берегов Греции и создать сильный отряд из трех броненосцев (включая "Императора Николая I", уже находившегося в составе эскадры) для возможного усиления военно-морских сил на Тихом океане.
Вопрос же кого послать, решался просто: выбирать было, практически, не из чего. "Петр Великий" к тому времени устарел, "Сисой Великий" - еще не окончен постройкой. Поэтому первоначально ГМЩ решил отправить на Средиземное море два самых новых корабля - "Гангут" и "Наварин". Однако 1 июня 1896 года, когда подготовка обоих броненосцев к дальнему плаванию шла полным ходом, главный командир Кронштадтского порта контр-адмирал С.О.Макаров предложил заменить "Гангут" броненосцем "Император Александр II", который, по его славам "не только находится в лучших условиях боевой готовности, но даже может быть изготовлен [к плаванию] в сравнительно меньший срок".
11 июля 1 896 года отряд под флагом контр-адмирала П.П.Андреева, назначенного начальником эскадры Средиземного моря, покинул Кронштадт. П.П.Андреев держал свой флаг на "Наварине" (командир капитан 1 ранга П.А.Безобразов), вместе с которым уходили "Император Александр П> (командир капитан 1 ранга К.Никонов), минный крейсер "Пасадник" (командир капитан 2 ранга Р.Н.Вирен) и два миноносца - № 119 (командир лейтенант А. Лебедев) и № 120 (командир лейтенант В.Нащинский).
После полуторамесячного перехода, посетив Киль, Христианзанд, Портленд, Кадикс и Алжир, корабли отряда 19 сентября 1 896 года бросили якорь на рейде Пирея.
15 сентября на пути из Алжира в Пирей броненосцы попали в 7-балльный шторм, сила ветра достигала 10 баллов. Размахи качки "Наварина" достигали 27°. Ударами волн на броненосце были сорваны все 16 крышек со световых машинных люков, сильные повреждения получили сами люки, пострадали дельные вещи из дерева, были выдавлены несколько иллюминаторов в кают-компании.
Очень опасными для корабля были волны, бившие в порты 152-мм орудий, но, к счастью, они выдержали испытание и на батарейную палубу попало лишь незначительное количество воды.
Из Пирея началось 15-месячное плавание "Наварина" в водах Эгейского и Средиземного морей. Броненосец представлял российский флаг в греческих и критских портах, одновременно проводилось обучение команды и необходимый ремонт. Уже во время перехода в Суду 1 3 октября 1 896 года, куда "Наварин" отправился сменить стационера - канонерскую лодку "Грозящий", на скорости броненосца сказалось влияние обрастания подводной части в теплых водах Средиземного моря: при 65 оборотах винта, что соответствовало скорости 12 уз, корабль фактически давал только 11,2 уз. Срочно требовалось докование, однако в начале 1 897 года на острове Крит произошел открытый конфликт греческой и турецкой общин, который привел к многочисленным человеческим жертвам. В конфликт вмешались правительства Греции и Турции, стала реальной угроза войны.
Поэтому Великобритания, Франция, Россия, Италии и Германия договорились о сборе международной эскадры для блокады Крита и о создании совета адмиралов.
Решением этого совета "Наварин" был направлен на рейд Ретимо, где нес дозорную службу совместно с английским крейсером "Scouth".
Днем оба корабля находились на якоре, а ночью ходили вдоль линии дозора от западной части мыса Майка до мыса Диако. Трудность ночного патрулирования усугублялась постоянной готовностью отразить атаку греческих миноносцев, неоднократно провоцировавших дозорные корабли.
4 марта броненосец "Император Николай!" сменил "Наварин", который ушел в Суду. 1 2 мая он вновь вернулся на рейд Ретимо, но уже 21 мая блокада была снята. 1 июля 1 897 года "Наварин" пришел в Полу, где встал в док для очистки подводной части от наростов и окраски. На переходе успели провести две торпедные стрельбы, во время первой из которых выпустили 15 торпед, во время второй - 20.
В конце 1 897 года центр международной напряженности переместился на Дальний Восток. Предстоял дележ сфер влияния. Столь же рьяно, как полтора года назад в Средиземном море, ведущие державы мира стягивали свои морские силы к берегам Китая и Кореи.
В Петербурге очередное Особое совещание четко определило, что "основные силы должны быть на главном театре, каковым для данного времени является Дальный Восток". Эскадре Тихого океана, состоявшей из крейсеров и канонерских лодок, срочно потребовалось усиление в виде хотя бы двух броненосцев, причем переброску кораблей следовало осуществить в кратчайшие сроки. Выбор, поэтому, пал на "Наварин" и "Сисой Великий", находившихся в Средиземном море. Обстоятельства заставляли корабли, проектировавшиеся и строившиеся в противовес Германии, все дальше уходить от Балтийских берегов.
В первых числах января 1898 года "Наварин" отправился из Суды на Дальний Восток, нагоняя "Сисой Великий", ушедший туда перед новым годом. В полдень 29 января с марса "Наварина" уведели "Сисой Великий" и дальше оба корабля шли уже вместе.
Из-за жары переход проходил в достаточно тяжелых условиях. 10 февраля капитан 1 ранга Иениш направил из Коломбо рапорт о неприспособленности броненосца к плаванию в жарком климате. Температура в бомбовых погребах, несмотря на вентяляцию, поднялась до 42°С, а в нижнем коридоре загорелся древесный уголь, заготовленный для корабельной кузницы.
Прибыв в Порт-Артур 16 марта 1898 года "Наварин" оставался там до апреля 1900 года в качестве флагманского корабля контр-адмирала О.В.Старка, командира Порт-Артурского порта и младшего флагмана эскадры.
В апреле 1900 года броненосец достаточно успешно действовал во время крупных совместных маневров эскадры и сухопутных войск, однако план боевой подготовки эскадры был нарушен: в Китае большой размах приобрело антииностранное движение "Ихэтуань" ("Отряды во имя мира и справедливости"), к которому присоединилось официальное правительство страны.
Эти события задевали интересы великих держав, которые к тому времени имели в Китае очень сильное экономическое и политическое влияние, фактически превратив его в полуколонию. В мае 1900 года на рейде китайского порта Таку начала сосредотачиваться международная эскадра. С 26 мая "Наварин", в составе отряда контр-адмирала М.Г.Веселаго, начал перевозку в Таку десантных отрядов, предназначенных для действий в составе "международных сил" против ихэтуаней и китайских войск. Перевозка сухопутных войск на боевых кораблях являлась вынужденной, из-за острой нехватки транспортов, мерой. "Транспортировка войск, с лошадьми и обозом на военных судах, лишая их боевой способности, возможна была только с китайцами, при полном бездействии их флота и, конечно, немыслима с более энергичным противником" - сообщал в рапорте на имя генерал-адмирала наместник на Дальнем Востоке адмирал Е.И.Алексеев. Так или иначе перевозка войск завершилась благополучно и в конце кампании, в сентябре 1900 года "Наварин" входил в состав международной эскадры, штурмовавшей Шан-хай-Гуань.
Десантной партии броненосца выпали наиболее тяжелые испытания. 71 моряка с "Наварина" и "Сисоя Великого" (один - с крейсера "Разбойник"), которыми командовали лейтенант барон фон Раден и мичман фон Ден. 18 мая прибыли в Пекин для охраны дипломатических миссий и вместе с отрядами других государств защищали посольские кварталы. Непрерывные бои с повстанцами и регулярными китайскими войсками продолжались два с половиной месяца - до 2 августа, когда на помощь подошли русские и американские войска. 13 человек (четырех убитыми и девять ранеными) потерял экипаж "Наварина".
После окончания "китайской кампании" "Наварин" оставался в составе эскадры Тихого океана. По утвержденной императором программе постепенного усиления состава эскадры некоторые корабли, в том числе и "Наварин", подлежали возвращению в Кронштадт, однако "лишь в том случае, если по политическому положению дел на Дальнем Востоке такое хотя бы временное ослабление состава нашей эскадры окажется возможным допустить". В результате 12 декабря 1901 года из Порт-Артура вышел, направлявшийся на Балтику для ремонта и модернизации, отряд контр-адмирала Г.П.Чухнина. В состав отряда входили, кроме "Наварина", еще два броненосца ("Сисой Великий" и "Император Николай I") и четыре крейсера ("Дмитрий Донской", " Владимир Мономах", "Адмирал Нахимов" и "Адмирал Корнилов").
Отряд прибыл в Либаву в конце апреля 1902 года. В мае "Наварин", вместе с другими кораблями, принял участие в военно-морском параде по случаю визита в Россию президента Франции Э.Лубе.
28 августа 1902 года ГМШ на основании "смотровых документов" возвратившихся из заграничного плавания кораблей, принял решение зачислить "Наварин" в программу плавания 1903 года в состав Учебно-артиллерийского отряда. Самые срочные работы по исправлению имеемых дефектов должны были быть выполнены в Ревеле силами порта Императора Александра III, а капитальный ремонт и модернизация, ради которых "Наварин" ушел с Дальнего Востока, отодвигались на неопределенный срок.
