На следующий день в полдень, пройдя мыс Финистерре, корабль взял курс на зюйд. Через сутки плавания случалась первая поломка. От интенсивной работы на волнении перетерся штуртрос. Сразу же управление рулем перевели в румпельное отделение. Назначенный для этого механик по звонкам и командам по переговорным трубам непосредственно у паровой машинки осуществлял управление рулем. Как ни парадоксально, но более надежным оказался ременный штуртрос, бывший на броненосце до Англии.
Спустя полтора часа боцманская команда сплеснила стальной штуртрос и корабль вновь получил управление из рубки.
Гибралтарский пролив прошли 26 марта. Впереди показались отвесные берега Африки, ярко освещенные и сильно отличавшиеся от европейских, окутанных туманом и мглой. Серые очертания укрепленной крепости Гибралтара, постепенно исчезая, стали едва видны. От большой разницы освещения здания и укрепления на африканском побережье, в отличие от строений на испанском берегу, казались белоснежными.
До самого прибытия в Алжир корабль подвергался сильной килевой качке, следуя при этом постоянно со скоростью 13 уз. 28 марта "Петр Великий" бросил якорь на Алжирском рейде. Этот 1500- мильный семидневный переход привел в восторг моряков, разбив при этом преувеличенные доводы скептиков о недостатках броненосца. "Качка хотя и была порядочная, но была такая плавная и ровная, что не производила никаких неприятных ощущений даже на новичков. Все любовались чудной картиной океана, высокими скалистыми берегами Испании и стадами морских касаток, игравших у самого борта. Одним словом, по общему отзыву капитана и всех офицеров, корабль "Петр Великий" обладает всеми качествами настоящего морского судна", – писал позже на страницах "Кронштадтского вестника" один из участников плавания.
Интересно отметить, что в те годы, уже во времена торжества паровой машины, традиционно высказывалась тревога по поводу отсутствия парусов даже у такого корабля, каковым являлся "Петр Великий". "Но скажет всякий, что без парусов "Петр Великий" далек от совершенства и способность корабля передвигаться только исключительно силою пара, без возможности приспособить его к передвижению силою ветра, ставит корабль этот в разряд судов, неспособных к океанскому переходу", – писалось далее в "Вестнике". Но автор сразу же успокаивал скептиков: "В кругосветное плавание "Петр Великий" не назначат, а что задачи вроде перехода в Средиземное море он исполнить может с успехом, не подвергаясь никаким авариям, доказывает наш настоящий переход".
Загрузившись углем в Алжире, корабль 7 апреля продолжил плавание в Пи- рей для соединения с отрядом контр-адмирала О. К. Кремера. Отряд кораблей, как тогда его называли "в греческих водах", был сформирован для политического присутствия России в Средиземном море. Базировались корабли, как правило, в портах Греции, предоставленных правящей династией Эллинов, где королевой тогда была дочь великого князя Константина Николаевича Ольга. Состав отряда был непостоянным и включал в себя корабли как Балтийского, так и Черноморского флота.
Прибыв в Пирей 11 апреля, "Петр Великий" стал флагманом. Здесь была самая продолжительная стоянка. 1 мая в командование отрядом вступил контр-адмирал П. А. Чебышев, назначенный на эту должность еще 5 апреля. Сразу же по прибытии он поднял свой флаг на "Петре Великом". В Пирее находились клипер "Забияка", крейсер "Азия" и шхуна "Туабсе". 6 мая, в день рождения цесаревича, будущего императора России, корабли отряда украсили флагами расцвечивания. Участвовали в празднике и находившиеся в Пирее французские корабли: фрегат "Флора", авизо "Жирондо" и "Буве" и греческие: фрегат "Эллас", броненосец "Георг" и канонерская лодка "Псара". Прибыл в Пирей и находившийся в Греции великий князь Константин Николаевич.
Через неделю контр-адмирал П. А. Чебышев произвел строевой смотр обеим ротам корабля (в первую роту входила верхняя команда, во вторую – нижняя: машинисты и кочегары), найдя их "в полной примерной исправности как в строевой, так и в хозяйственных частях".
20 мая "Петр Великий" посетили король и королева Эллинов со своей многочисленной свитой. В кают-компании по традиции состоялся обед. Под вечер, после отъезда на берег королевской четы, был устроен фейерверк. На следующий день ответный визит совершили свободные от вахты офицеры. 22 мая из мастерских порта на броненосец доставили два торпедных аппарата, оставленных незадолго до этого фрегатом "Генерал-Адмирал". В этот же день из Пирейской бухты перешли во Флоренскую, определив по створам девиацию компасов и циркуляцию, которая при положении руля на борт совершалась в течение 4,5 минут и составляла в диаметре 3,5 каб. Затем из установленных в Глазго двух новейших скорострельных пушек Гочкиса произвели стрельбу. Эти орудия установили специально для борьбы с миноносцами – новым типом боевых кораблей, носителями самодвижущихся мин Уайтхеда (торпед). 27 мая из Флоренской бухты корабль ушел в Корфу.