После гибели российского флота в дальневосточных водах на Балтике остались одни "старые калоши", и морское ведомство в лице морского министра вице-адмирала Бирилева потребовало срочно возвратить обратно хотя бы те крохи, что остались от тихоокеанских эскадр. Владивостокские крейсера и корабли, интернированные в Китае и Маниле, получили приказ срочно следовать в Балтийское море. Для отряда Энквиста был определен маршрут: Сайгон - Коломбо - Джибути - Порт-Саид - Неаполь - Виго - Шербур - Либава. На переходе в Сайгон, где находился крейсер "Диана", выяснилось, что скорость крейсера "Олег" за счет обрастания корпуса уменьшилась на два узла. Необходимо было срочно провести докование.
В Сайгоне пришлось задержаться. После ввода "Олега" в док приступили к очистке и окраске днища. Запланированное в морском штабе соединенное следование одним отрядом не состоялось: корабли уходили поодиночке, по мере готовности. Одновременно шла перетасовка офицеров. Ушел "Цесаревич", прихватив с "Олега" лейтенанта Политовского. Самым беспокойным контингентом на кораблях были запасные, поэтому их решили списать и отправить отдельным эшелоном на транспорте "Ливония". В частности, с "Олега" списали 100 нижних чинов, призванных из запаса в 1904 г.; начальником эшелона назначили лейтенанта Афанасьева.
Для пополнения некомплекта офицеров и команды на "Олег" перевели с прибывшего "Алмаза" шесть офицеров (в их числе был мичман Китицын - будущая гордость российского подводного флота), а также 38 нижних чинов. "Аврора", "Алмаз" и "Олег" снялись с якоря 26 ноября и взяли курс на Коломбо. На переходе участились выходы из строя котлов и рулевого управления - сказались длительное бездействие и обновление личного состава.
На кораблях происходило брожение среди матросов, вызванное слухами о событиях в России. Адмирал Энквист обратился в главный штаб с просьбой прояснить обстановку. По приходу в Коломбо капитан 1 ранга Добротворский зачитал и разъяснил команде "Олега" высочайший манифест от 17 октября о даровании гражданских свобод.
Салютом в 31 выстрел отметили тезоименитство царя. Загрузив 900 т угля и приняв 10 быков, "Олег" в составе отряда покинул Коломбо и направился к Баб-эль-Мандебскому проливу. Переход проходил при периодической течи холодильника, отчего повышалась соленость котельной воды, определять которую приходилось на вкус, пробуя воду через каждые 20 минут. Отключали одну из машин, скорость падала, при этом трудно было удержать корабль на курсе.
Прибыв 21 декабря в Джибути, на "Олеге" провели продувку котлов водой, чтобы уменьшить соленость. Тогда же корабль начали перекрашивать в черный цвет. По случаю Рождества адмирал поздравил экипажи и амнистировал всех арестованных. Общими усилиями офицеров и команды на "Олеге" устроили спектакль, среди зрителей были Энквист и одно отделение с крейсера "Алмаз". На другой день часть команды крейсера была приглашена на спектакль, поставленный на "Авроре".
Доставленный на баржах уголь командир и механик "Олега" забраковали как негодный; после переговоров с поставщиками удалось получить желанный кардиф. Для сжигания в котлах делали смесь кардифа с вестфальским углем, горение было сносное, но расход топлива увеличился.
1 января 1906 г. застало "Олега" и "Аврору" в Красном море; "Алмаз" покинул Джибути несколько раньше. При проходе Суэцкого канала из-за неисправности телемотора "Олег" сошел с курса и сел на бровку канала перед самым Порт-Саидом. К счастью, крейсеру удалось сняться своим ходом. Ремонт телемотора выполнили силами экипажа, для пополнения магистрали истратили три пуда глицерина.
При следовании Средиземным морем трубки в котлах "Олега" начали лопаться по несколько штук сразу. При ремонте котла № 4 кочегары Подгайло и Письменный добровольно влезли в еще горячий котел - первый официально зафиксированный случай в истории российского флота. Но реакция адмирала Бирилева на рапорт Энквиста о необходимости ремонта машин и котлов "Олега" была быстрой и решительной. В Алжир, куда прибыл отряд, направили следственную комиссию во главе с полковником КИМФ Ведерниковым, которого уполномочили заказать запасные трубки для котлов и холодильников, но замену приказали производить своими силами и на ходу.
Однако осмотр механизмов, проведенный Ведерниковым, показал, что без основательного ремонта крейсер двигаться дальше не сможет. Скрепя сердце вице-адмирал Бирилев разрешил ремонт, хотя и урезал на неделю время стоянки в Алжире. Адмирал со штабом перешел на "Олег". На уходящую в одиночку "Аврору" были списаны нижние чины сроков службы 1898 и 1899 гг., среди них был рулевой квартирмейстер Магдалинский, написавший впоследствии книгу о плавании на крейсере "Олег".
За время стоянки в Алжире произошел ряд инцидентов. 21 января 1906 г. налетел сильный шквал, на "Олеге" лопнула скоба бриделя мертвого якоря. Пока отдавали собственный якорь, крейсер навалился бортом на баржу, а кормой - на брекватер. Завели на мертвый якорь стальной перлинь, срочно доставленный с "Авроры", и, выбирая его с помощью носового шпиля, сошли с камней. Осмотрели повреждения подводной части - за счет деформации руль поднялся на четыре дюйма.
На одном из пароходов в порту вспыхнул пожар, в тушении которого участвовала шестерка с 14 нижними чинами с мичманом Китицыным и прапорщиком Добрыниным. Позже на подмогу с "Олега" был направлен барказ с насосами и другим оборудованием.
Катаясь на велосипеде по городу, капитан 1 ранга Добротворский попал под автомобиль и был помещен в госпиталь с серьезными ранами. В командование крейсером вступил старший офицер капитан 2 ранга Посохов, на его место был назначен лейтенант Мантуров, а исполнять должность старшего штурманского офицера стал лейтенант Шуберт.
5 февраля на "Олеге" подняли флаги расцвечивания и произвели салют по случаю вступления в должность французского президента Фальера. В тот же день на рейд прибыл крейсер 1 ранга "Богатырь". Его машинная установка, изготовленная в Германии, работала безукоризненно, чему экипаж "Олега" мог только позавидовать. Одним из праздничных мероприятий стал поставленный экипажем "Олега" спектакль "Тарас Бульба", на который были приглашены зуавы из расквартированного в окрестностях Алжира полка и матросы с французских миноносцев, а также делегация с "Богатыря".
В ходе ремонта на "Олеге" заменили часть питательных трубок в котлах и холодильниках, произвели щелочение котлов и последующую очистку трубок от толстого слоя накипи. Последняя операция выполнялась с помощью электрического приспособления, восемь комплектов которого были закуплены на местном заводе. 16 февраля, почти уложившись в срок, установленный морским министром, крейсер покинул Алжир. При ясной нежаркой погоде он пересек Бискайский залив и в конце февраля прибыл в Шербур. Там приняли угольный брикет и, не задерживаясь, двинулись дальше; наваленное на верхней палубе топливо убирали в угольные ямы уже на ходу.
В Северном море "Олег" попал в жестокий шторм и получил многочисленные повреждения палубных устройств и плавсредств. По ранее полученному разрешению крейсер прошел Кильским каналом (при этом дважды коснулся грунта) и 3 марта вышел в Балтийское море. Кстати, трубки в котлах продолжали лопаться не менее часто, чем до ремонта в Алжире. В пасмурную субботу, 4 марта, прибыли на рейд Либавы, отслужили благодарственный молебен и начали готовиться к смотру - чистили палубу песком, мыли борта и надстройки. На следующий день вице-адмирал Скрыдлов и контр-адмирал Ирецкой, который в прошлом году провожал крейсер в поход, провели смотр по полной форме "с тревогами и опросом претензий".
6 марта "Олег" вошел в бассейн либавского порта. Началась подготовка документов на увольнение нижних чинов. Для ревизии машин прибыл главный инспектор по механической части. Одновременно приехал и вступил в должность капитан 1 ранга Добротворский.
