Во время кризиса в отношениях с Англией в 1863 г. в связи с мятежом буйного панства в Привисленском крае единственный находившийся на Средиземном море русский фрегат «Ослябя» был срочно отправлен в Нью-Йорк на соединение с эскадрой контр-адмирала С.С. Лесовского. Взамен с Балтики был прислан фрегат «Олег», прибывший 16 сентября 1863 г. на Тулонский рейд. 25 октября фрегат покинул Тулон и через 6 дней бросил якорь в греческом порту Пирей. За время перехода из Кронштадта в Пирей «Олег» находился в море 24,5 суток, то есть среднесуточное плавание его составляло 189 миль.
Независимо от фрегата «Олег» в Средиземном море в 1863 г. крейсировал и черноморский корвет «Сокол».
16 августа 1864 г. через Гибралтарский пролив проследовал фрегат «Александр Невский», шедший из Америки. 29 августа фрегат прибыл в Пирей. С 24 сентября по 4 октября «Александр Невский» крейсировал в Восточном Средиземноморье.
28 октября 1864 г. командующий русской эскадрой на Средиземном море контр-адмирал Лесовский получил указание от «Государыни Императрицы идти в Геную и заняться катанием на судах эскадры Высочайших особ».
30 октября фрегат «Александр Невский» вместе с корветом «Витязь» прибыл в Геную. Там на борт фрегата поднялся цесаревич Николай Александрович. Затем «Невский» в сопровождении «Витязя» отправился в круиз для цесаревича с заходом в Виллафранку и Ливорно. К концу декабря на рейде Виллафранки собрались фрегаты «Александр Невский» и «Олег» и корвет «Витязь».
Можно только гадать, кому и зачем потребовалось устраивать зимнее морское путешествие для цесаревича Николая, страдавшего тяжелым легочным заболеванием? О том, зачем надо было гонять фрегат и корвет даже говорить не приходится.
Состояние наследника престола резко ухудшилось, и в ночь с 11 на 12 апреля 1865 г. он умер в Ницце. Тело Николая Александровича было доставлено на фрегате «Александр Невский», который 17 апреля в сопровождении фрегата «Олег», корвета «Витязь» и клипера «Алмаз» отправился к Гибралтару. 21 мая 1865 г. эскадра благополучно пришла в Кронштадт. 25 мая тело наследника было перегружено с фрегата на яхту «Александрия» для перевозки в Петропавловский собор в Петербурге.
31 мая 1867 г. фрегат «Александр Невский» под командованием капитана 2-го ранга Кремера вышел из Кронштадта и отправился в крейсерство в Атлантику.
27 июля «Александр Невский» прибыл в порт Кадис (Испания). 4 июля на фрегате поднял свой флаг контр-адмирал Посьет, и на фрегат прибыл 17-летний мичман великий князь Алексей Александрович. 10 июля «Александр Невский» снялся с Кадисского рейда под парами, при полном безветрии, а с рассветом следующего дня, получив тихий юго-восточный ветер, вступил под паруса.
В новом крейсерстве фрегат спустился до островов Зеленого мыса, а затем вернулся в Кадис, куда и прибыл в полдень 21 августа. На обратный путь длиной в 2900 миль потребовалось 19 дней.
В полдень 28 августа 1867 г. «Александр Невский» покинул Кадис и отправился в Средиземное море. 13 сентября Алексей Александрович был произведен в лейтенанты. 11 октября фрегат прибыл в Пирей. В тот же день великий князь Алексей оставил фрегат, и контр-адмирал Посьет спустил свой флаг.
Замечу, что и здесь поездка великого князя Алексея носила не только туристический характер. Дело в том, что в 1863 г. Национальная ассамблея Греции выбрала королем эллинов датского принца Вильгельма, сына наследника датского престола, который позже станет королем Кристианом IX. Оный Вильгельм стал царствовать под именем Георгия I. Любопытно, что его родная сестра Дагмар вышла замуж за цесаревича Александра Александровича и в 1881 г. стала императрицей Марией Федоровной. Но это не всё — в 1867 г. дочь генерал-адмирала великая княгиня Ольга Константиновна стала женой короля Георга I Греческого.
Так что в Афинах родни у великого князя Алексея хватало. Соответственно и ранее неплохие отношения с Грецией еще улучшились.
В Пирее фрегат «Александр Невский» поступил в состав эскадры капитана 1-го ранга Ивана Бутакова, который 13 сентября 1867 г. поднял на нем свой брейд-вымпел.
2 марта 1868 г. уже контр-адмирал Иван Бутаков получил по телеграфу депешу от управляющего Морским министерством о назначении фрегата «Александр Невский» в практическое плавание с его императорским высочеством великим князем Алексеем Александровичем. Но так как фрегат нуждался в некоторых необходимых исправлениях, то он был отправлен 8 марта из Пирея в Тулон, куда и прибыл благополучно 23 марта, зайдя по пути в Неаполь.
Исправления фрегата и приготовления к предстоявшему плаванию продолжались до мая. Наконец 3 мая 1868 г. «Александр Невский» оставил Тулонский рейд и 10 мая прибыл на Палермский рейд, сделав почти весь переход под парусами.
11 мая, закончив погрузку угля, снялись с Палермского рейда при совершенном штиле и прошли под парами через Мессинский пролив. 12 мая в 7 часов вечера вступили под паруса.
27 мая фрегат оставил Смирнский рейд, прошел Дарданеллы и 29 мая прибыл в Буюк-дере.