25 ноября крейсер вышел в море и, следуя на юг вдоль португальского берега, впервые встретил значительную океанскую зыбь от норд-веста. Размахи качки доходили до 20°. Днем 27 ноября прошли Гибралтарский пролив. Уже в Средиземном море, вблизи единственного в его западной части о. Альборан (Испания), провели практическую стрельбу из орудий. И здесь, стремясь форсировать боевую подготовку, командир A.M. Доможиров, не считая первых и вторых комендоров, привлек к стрельбе почти весь офицерский состав, включая великого князя. Для демонстрации личному составу и проверки разрывного действия чугунных гранат сделали пять боевых выстрелов из 75-мм орудия. "Разрывы получились очень хорошие…", – писал в своем строевом рапорте А. М. Доможиров. Ученик и последователь прогрессивных русских адмиралов И.Ф. Лихачева и А.А. Попова, он, очевидно, хорошо помнил завет последнего – "корабли строятся для пушек". Из этого опыта он сделал вывод о необходимости увеличить на кораблях количество учебных стрельб, особенно подготовительных, которые не вызывают больших расходов и в то же время доставляют личному составу "крайне желательную полезную практику".
На переходе в Средиземное море A.M. Доможиров приступил к опытам по определению экономичности средней машины в сравнении с бортовыми. По опыту трехсуточных замеров оказалось, что средняя машина при 9-узловой скорости (индикаторная мощность 1956 л.с.) требует расхода угля 72 т/сут. (без учета 10 т на общекорабельные потребности и 4 т на пополнение котлов). Бортовые же машины даже при большей скорости (9,4 уз) требовали только 68 т/сут. При уравнивании расхода угля в них со средней машиной скорость повышалась до 10,5 уз, и преимущество бортовых машин становилось еще более явным. Причины такого несоответствия практики с проектными предположениями A.M. Доможиров видел в значительной затрате части мощности средней машины на преодоление сопротивления винтов (хотя и вращавшихся свободно при разобщении) бортовых машин.
Днем 29 ноября, совершив 970-мильный переход от Виго за 4 дня, пришли в Алжир, где застали направлявшийся также в Тихий океан крейсер "Владимир Мономах". Все пять дней стоянки "Россию" с утра до вечера переполняли толпы жаждущих побывать в гостях у русских.
Выйдя из Алжира 5 декабря, проверили остаточную девиацию магнитных компасов, на которую могла повлиять проведенная ранее стрельба, и продолжили путь вдоль берегов Алжира и Туниса. 7 ноября произвели поверочную стрельбу. Попадания были, по донесению командира, вполне удовлетворительные, орудия и станки действовали исправно, поломок и повреждений не обнаружили. Днем продолжили путь на восток и утром 8 декабря вошли в гавань порта Ла-Валлетта на Мальте. На рейде застали возвращавшийся из Тихого океана броненосец "Император Николай I" и английскую эскадру Средиземного моря.
Следующим пунктом назначения была бухта Суда на о. Крит.
Давший миру великую, за 2-3 тысячи лет до н.э. сформировавшуюся крито-микенскую культуру, этот многострадальный остров, находившийся под властью Османской империи, многие годы терзали кровавые национальные междоусобицы. Вспыхнувшее в феврале 1897 г. восстание христианского населения, требовавшего присоединения острова к Греции, привело к греко-турецкой войне и высадке греческого десанта на остров. Флоты великих держав пытались остановить конфликт, были даже сделаны попытки организовать блокаду острова, чтобы прекратить бои и полыхавшие над островом пожары. И хотя Турция победила на материке, под давлением держав она была вынуждена согласиться на предоставление Криту широкой автономии. Комиссаром острова после долгих дебатов в 1898 г. согласились признать принца Георга Греческого. Роль держав-покровительниц Крита взяли на себя Англия, Россия, Франция и Италия, и бухта Суда оставалась местом стоянки их кораблей.
Русский флот в конце 1897 г. представляли здесь броненосцы "Император Николай I", "Император Александр II", "Наварин" и "Сисой Великий".
На следующий день по прибытии "России" – 19 декабря – командующий русской эскадрой контр-адмирал П.П. Андреев провел инспекторский смотр крейсеру с опросом претензий команды. Из иностранных кораблей на рейде своим симметричным силуэтом, одной мачтой между двух труб и башнями с 343-мм орудиями заметно выделялся итальянский броненосец "Сардиния".