Утром 24 июня снялись с якоря под парами, а, дойдя до мыса Бач Хэад (Англия), поставили паруса и лавировали, не прекращая паров. Но вскоре из-за недостатка угля пары прекратили и вновь развели на фрегате только 28 июня, в 25 милях от Эдистонского маяка, где взяли на буксир корвет. 29 июня отряд бросил якорь на Фальмутском рейде.
5 июля снялись с якоря с Фальмутского рейда и вечером того же дня, миновав камни Манакле, поставили паруса, а на фрегате прекратили пары. Ветер был попутный, но недолго. К вечеру слег дующего дня сделалось маловетрие с туманом, которое продолжалось до 7 июля. Наконец 8 июля развели пары и 11 июля прибыли на Лиссабонский рейд.
29 июля отряд достиг острова Мадейра, а 4 августа повернул обратно в Россию.
6 октября 1866 г. «Ослябя» и «Витязь» прибыли в Кронштадт. На обратном пути под парами отряд шел всего 42 часа, остальное время шли под парусами.
В следующем году великий князь Алексей был за это плавание представлен к чину мичмана.
31 мая 1867 г. фрегат «Александр Невский» под командованием капитана 2-го ранга Кремера вышел из Кронштадта и отправился в крейсерство в Атлантику.
27 июня «Александр Невский» прибыл в порт Кадис (Испания). 4 июля на фрегате поднял свой флаг контр-адмирал Посьет и прибыл на фрегат великий князь Алексей Александрович. 10 июля «Александр Невский» снялся с Кадисского рейда под парами, при полном безветрии, а с рассветом следующего дня, получив тихий юго-восточный ветер, вступил под паруса.
В новом крейсерстве фрегат спустился до островов Зеленого мыса, а затем вернулся в Кадис, куда и прибыл в полдень 21 августа. На обратный путь длиной в 2900 миль потребовалось 19 дней.
В полдень 28 августа 1867 г, «Александр Невский» покинул Кадис и отправился в Средиземное море, 11 октября фрегат прибыл в Пирей. В тот же день великий князь Алексей оставил фрегат, и контр-адмирал Посьет спустил свой флаг.
В Пирее «Александр Невский» поступил в состав эскадры капитана 1-го ранга Бутакова, который 13 сентября поднял на нем свой брейд-вымпел.
2 марта 1868 г. контр-адмирал Бутаков получил по телеграфу депешу от управляющего Морским министерством о назначении фрегата «Александр Невский» в практическое плавание с его императорским высочеством великим князем Алексеем Александровичем. Но так как фрегат нуждался в некоторых необходимых исправлениях, то он был отправлен 8 марта из Пирея в Тулон, куда и прибыл благополучно 23 марта, зайдя по пути в Неаполь.
Исправления фрегата и приготовления к предстоявшему плаванию продолжались до мая. Наконец, 3 мая 1868 г. «Александр Невский» оставил Тулонский рейд и 10 мая прибыл на Палермский рейд, сделав почти весь переход под парусами.
11 мая, закончив погрузку угля, снялись с Палермского рейда при совершенном штиле и прошли под парами через Мессинский пролив. 12 мая в 7 часов вечера вступили под паруса.
27 мая фрегат оставил рейд, Смирн прошел Дарданеллы и 29 мая прибыл в Буюк-дере.
31 мая фрегат оставил Буюк-дере и вскоре вышел под парами в Черное море. Отойдя от пролива 20 миль, вступили под паруса. В течение следующих четырех суток ветер упорно держался между северо-северо-западным и северо-северо-восточным, днем настолько свежий, что принуждал брать рифы, а ночью совсем стихал. А 4 июня и вовсе заштилило, поэтому развели пары, и 5 июня фрегат благополучно прибыл на Одесский рейд.
Оставив Одессу 11 июня, «Александр Невский» под парусами при легком попутном ветре за 7 дней дошел до Поти. 18 июня, подходя к Поти, в 6 милях от порта заштилило. Но так как опасно было оставаться на ночь близко от берега без ветра и желая как можно скорее встретиться с генерал-адъютантом Посьетом, который ожидал прибытия фрегата, то в 6 часов вечера развели пары в двух котлах и в 8 часов прибыли благополучно на якорную стоянку.
Однако здесь не нашли никаких известий от адмирала Посьета, но по телеграфу тотчас же донесли в Тифлис о прибытии фрегата.
Плавание от Тулона до Поти проходило, когда только позволяли обстоятельства, под парусами. Но, имея в виду главнейшее условие — своевременное прибытие фрегата к месту назначения и встречая почти постоянно штили или легкие противные ветры, как и следовало ожидать в это время года, — иногда разводили пары. И в этих случаях фрегат почти всегда шел средним или малым ходом, отчего терял время, но сберегал котлы и выигрывал в топливе, которого за все время было сожжено 480 тонн, то есть меньше штатного запаса фрегата. И еще следует отсюда вычесть около 45 тонн, употребленных на опреснение воды и на варку пищи. Следовательно, на ход ушло только 435 тонн.
Плавание от Тулона до Поти можно разделить следующим образом: всего расстояние составило 2555 миль, из этого пройдено под парусами 1385 миль и под парами 1170 миль. По времени получилось следующим образом: под парусами 23 дня 10 часов, под парами 6 дней 22 часа и на якоре 15 дней 28 часов. Всего 46 дней, считая от 3 (15) мая, когда вышли из Тулона, и до 18 (30) июня — дня прихода в Поти.