21 августа 1893 года крейсер вышел из Кронштадта на соединение со Средиземноморской эскадрой. Местом дислокации Средиземноморской эскадры был греческий порт Пирей, откуда корабли уходили для посещения разных портов Средиземноморья. В остальное время в исторической Саламинской бухте или на рейде острова Порос занимались повседневной боевой подготовкой и корабельными учениями. Эта служба для «Азова» продолжалась до конца 1894 года.

22 ноября 1894 года крейсер покинул Пирей, чтобы передислоцироваться на Дальний Восток. Срочность отплытия была такова, что судовой праздник, день святого Георгия, приходившийся на 26 ноября, команде пришлось отмечать в пути. По пути к новому месту службы корабль поочередно вел на буксире два вновь построенных минных крейсера – «Всадник» и «Гайдамак».

6 февраля 1895 года «Память Азова», завершив второе плавание на Дальний Восток, пришел в Нагасаки, где на нем подняли флаг командующего Тихоокеанской эскадрой вице-адмирала П.П. Тыртова. В силу предписанных японским правительством правил, эскадра была разбросана по различным портам Японии. В Нагасаки стояли крейсера «Память Азова» и «Владимир Мономах». 6 апреля к ним присоединился флагманский корабль эскадры Средиземного моря броненосец «Император Николай Первый» под флагом контр-адмирала С.О. Макарова.

В конце апреля корабли эскадры начали сосредотачиваться в китайском порту Чифу. Ввиду уведомления о возможном начале боевых действий со стороны Японии эскадра готовилась к сражению. Был издан революционный для флота приказ о немедленном окрашивании кораблей в защитный «светло-серый цвет». Командиры использовали эту возможность, чтобы подобрать наиболее эффективный цвет окраски. Крейсер «Память Азова» был окрашен в розовато-серый цвет под тон цвета местности, в результате чего не только ночью, но и вечером и рано утром корабль совершенно сливался с морем. Тогда же эскадры Тыртова и Макарова впервые вышли в море для отработки эскадренных эволюций. Крейсер «Память Азова» возглавлял правую колонну, в которой шли крейсера «Адмирал Корнилов» и «Рында».

Вскоре Япония отказалась от претензий на Ляодунский полуостров. С наступлением разрядки в обстановке Тихоокеанская эскадра покинула Чифу. 29 июня «Память Азова» под флагом вице-адмирала Тыртова ушел во Владивосток. На долгие годы крейсер стал главной ударной силой Тихоокеанского флота. За это время он успел пережить четверых командующих флотом (вице-адмирала Тыртова, контр-адмирала Алексеева, контр-адмирала Дубасова и вице-адмирала Гильдебрандта) и трех командиров (капитанов 1-го ранга Чухнина, Вирениуса и фон Нидермиллера).

Главным событием этого времени стала передача в 1898 году русскому флоту Порт-Артура; в числе первых кораблей в новый порт прибыл и «Память Азова». Именно он своим салютом приветствовал Андреевский флаг, который 16 марта на мачте Золотой Горы поднял великий князь Кирилл Владимирович. В Порт-Артуре крейсер простоял всю весну и лето, после чего, после нормализации обстановки, возобновил стационарную службу в других портах.

В конце 1899 года крейсера на Тихом океане сменили броненосцы, и «Память Азова» решено было вернуть на Балтику. 28 ноября крейсер вышел из Владивостока и в следующем году с открытием весенней навигации встал на рейде Кронштадта.

В 1900 году решено было перевооружить корабль, заменив котлы и освободив их от устаревшей магистральной трубы водоотливной системы. Летом 1901 года крейсер в качестве флагмана Учебного артиллерийского отряда принимает участие в показательных маневрах флота.