Уже 9 июня 1901 г. последовало приказание управляющего Морским министерством сразу же после спуска из каменного эллинга Нового Адмиралтейства броненосца "Бородино" начать постройку нового крейсера типа "Богатырь" взамен погибшего в огне. Все заказанное и заготовленное для "Витязя" оборудование передавалось на новый корабль, несмотря на настойчивые просьбы командования Черноморского флота направить все это оборудование для строящегося "Очакова", чтобы подготовить его к юбилею Севастопольской обороны. Пока же все отделы МТК и ГУКиС занялись восстановлением утраченной на пожаре документации. А.И.Мустафина, который был оставлен строителем нового крейсера, и мастеровых перевели в Новое Адмиралтейство, где уже приступили к подготовительным работам.
Генерал-адмирал на закладке "Очакова" в Севастополе, после ознакомления с чертежами, распорядился не устанавливать на него надводные минные аппараты. Для управляющего морским министерством было неясно, распространяется ли это указание на остальные крейсера. Поскольку великий князь отбыл в любимый им Париж, то вопрос пришлось отложить до его возвращения. Впоследствии выяснилось, что генерал-адмирал считал надводные минные аппараты весьма опасными для носителей и приказал оставить их только на минных судах. Кроме того, рельсовую подачу снарядов он потребовал устроить не по типу "Дианы", где она "мешает ходить", а иначе.
В связи с тем, что форштевень для "Витязя" уже отлили с утолщением для отверстия минного аппарата, корабельный инженер Скворцов предложил заменить его верхнюю часть на штампованную из двух листов стали и при этом использовать снятую часть в качестве штампа. Инженер считал, что для быстроходного крейсера иметь подобное утолщение невыгодно. Управляющий Морским министерством рассудил прагматично: раз уж форштевень изготовлен, то так и надо оставить. Для "Очакова" и "Кагула" форштевни отлили без отверстий, так черноморские крейсера получили видимое отличие от балтийских.
Сразу после принятия решения о строительстве крейсера в Новом Адмиралтействе приступили к разбивке на плазе. В первых числах сентября прошел спуск на воду броненосца "Бородино", а через два месяца началась сборка корпуса нового крейсера. Еще накануне постройки (8.11.1901) он получил наименование "Олег" - в память парусно-парового фрегата, погибшего от тарана броненосной батареи "Кремль". А "Витязь" еще летом исключили из списков флота. Причислили же "Олег" к тому же 18-му экипажу.
Поскольку в ходе строительства "Богатыря" выявилась теснота в подбашенных отделениях, на "Олеге" их расширили за счет погребов, которые перенесли в помещения ликвидированного минного погреба. Мины заграждения, предусмотренные проектом, сняли вообще.
Для ускорения производства машин было достигнуто соглашение с фирмой "Вулкан" о передаче Обществу Франко-Русских заводов моделей для ряда деталей, общим числом 23. Здесь же обрабатывались паровые цилиндры машин. В Риге отлили станины, а в Швеции изготовили испарительные трубки для котлов. В Англии частным порядком заказали восемь питательных насосов. Для наблюдения за постройкой был назначен старший инженер-механик Моэлин (позже, по здравой традиции русского флота, он занял должность старшего судового механика в экипаже "Олега").
Руководство завода собиралось командировать своих сотрудников на предстоящие испытания крейсера "Богатырь", морское ведомство согласилось включить их в число своих представителей, однако немцы категорически отказались принимать конкурентов из России, равно как и запретили снимать чертежи с натуры ряда вспомогательных агрегатов, ссылаясь на коммерческую тайну.
Благодаря приобретенному на "Витязе" опыту, а также чертежам, поступающим из Германии, работы по сборке корпуса шли довольно споро, и 6 июля 1902 г. состоялась официальная закладка в высочайшем присутствии. Император собственноручно покрыл раствором сурика отсек в кильсоне на втором дне и заложил в него помещенную в замшевый чехол серебряную дощечку. Отсек сверху был накрыт листом обшивки с отверстиями под заклепки, первую из которых заклепал Николай II, а следующую - императрица, наследник престола и далее по чинам по нисходящей линии. По окончании церемонии на флагштоках в носу и корме были подняты соответствующие флаги.
В начале октября начались испытания наливом воды водонепроницаемых отсеков второго дна между шп. 36 - 41, 46 - 51, 56 - 60, 74 - 78. К концу месяца таким же образом проверили и остальные отсеки второго дна. После установки шпангоутов до броневой палубы и бимсов были сняты шаблоны по месту, и на бронепрокатном заводе по ним изготовили необходимое количество плит. После того, как плиты заняли свои места, приступили к установке шпангоутов над броней, а затем - к клепке обшивки, палубных бимсов и самих палуб. Вслед за клепальщиками к работе приступали рубщики, удалявшие избытки металла с листов обшивки, за ними следовали чеканщики, которые обеспечивали водонепроницаемость заклепочных швов.
В конце ноября комиссия Главного гидрографического управления определила места установки компасов на "Олеге": в боевой и рулевой рубках, в рулевом отделении и центральном посту. Главный носовой компас располагался на рубке, где все его окружающие конструкции изготавливались из немагнитного сплава.
Попытка внедрить на русских судах металлическую мебель по примеру американцев, оснастивших ею "Варяг", не удалась, хотя из США были доставлены подробные чертежи, снятые с натуры. Заводчиков, которые бы взялись за освоение новой технологии, не нашлось, поэтому мебель по-старинке заказали из дерева.
Спуск "Олега" на воду состоялся 14 августа 1903 г. К полудню на Новое Адмиралтейство прибыл на катере Николай II со свитой и членами семьи. Командир порта вице-адмирал Де-Ливрон отдал рапорт государю и преподнес дамам букеты, перевитые лентами с названием спускаемого корабля. Император поднялся на палубу крейсера, где принял рапорт от командира корабля капитана 1 ранга Лебедева, поздоровался с выстроенной здесь же командой, после чего направился в царский шатер.
В 12.25 светло-серый корпус с ярко-красной подводной частью сошел в воды Невы под крики "ура" и залпы салюта со специально вытребованного из Ревеля крейсера "Азия". После доклада об отсутствии течи и перегиби императорская семья убыла на катерах в Петропавловский собор.
Вскоре "Олег" отбуксировали к Франко-Русскому заводу для установки машин и котлов. По плану его должны были представить через год после спуска на испытания и еще через год отправить на Дальний Восток. Причем разразившаяся в начале 1904 г. внезапная война с Японией поначалу никак не отразилась на темпах достройки кораблей, в том числе и "Олега"; все шло неспешно.
Новые обстоятельства - прежде всего, гибель броненосца "Петропавловск" вместе с вице-адмиралом Макаровым - заставили российское руководство пересмотреть дальнейшие планы войны и всерьез готовить помощь флоту на Дальнем Востоке. Были экстренно отпущены ассигнования на достройку кораблей, в том числе и "Олега", что позволило, форсируя работы, подготовить его к испытаниям. В апреле появилось решение о формировании 2-й эскадры флота Тихого океана во главе с контр-адмиралом - З.П.Рожественским. "Олег" был включен в ее состав, а на должность командира крейсера назначен только что вернувшийся из Средиземного моря капитан 1 ранга Л.Ф.Добротворский*.
24 июня 1904 г. в 8.00 на "Олеге" подняли вымпел, гюйс, флаг и вступили в кампанию. К тому времени на корабле уже были смонтированы лебедки Темперлея, на мачты с помощью крана установлены стеньги и стрела для подъема паровых катеров. Произошли и первые поломки: при отдаче якоря лопнул корпус стопора Легофа, а при отбивании склянок треснул судовой колокол.
На следующий день в 9.00 отдали швартовы, опробовали машины, с помощью портовых буксиров развернулись по течению Невы и под проводкой двух лоцманов пошли Морским каналом в Кронштадт. Там была проведена частная проба машин для определения правильности сборки, которая оказалась вполне удачной. При изменении числа оборотов до 110 нагревания подшипников и других трущихся частей не обнаружилось. Первый рейс "Олег" совершил под шестью котлами до маяка Стирсуден. 23 августа крейсер ввели в Константиновский док для осмотра и покраски подводной части. В 14.00 его посетил Николай II со свитой. Император в сопровождении адмиралов Авелана, Бирилева и Рожественского осмотрел корабль. Через несколько дней на крейсере побывала и гостившая в Петербурге королева эллинов Ольга Константиновна.
26 августа, окончив окраску подводной части, крейсер покинул док. Заводская проба машин оказалась неудачной, вышли из строя стопорные клапаны, пришлось вернуться обратно. Завод обещал устранить неисправность за 10 дней.
В первых числах сентября начались ходовые испытания на мерной миле. Приступила к работе комиссия во главе с флагманским инженер-механиком Похолкиным.
Ввели в действие все котлы, но при попытке развить полный ход обнаружили стук в ЦНД. Испытания пришлось приостановить. На крейсере продолжало работать 417 мастеровых.
8 сентября у маяка Стирсуден произвели отстрел артиллерии. Израсходовано снарядов: 152-мм - 180, 75-мм - 85, 47-мм - 60, 37-мм - 20, 7,62-мм пулеметных патронов - 200 шт. В командирской и сигнальной рубках разбилось три стекла; других замечаний не было.
При разборке заднего ЦНД правой машины на его внутренней поверхности по всей высоте были обнаружены многочисленные борозды глубиной 1 мм и шириной около 2 мм, а также трещины силовых элементов. Кроме того, лопнула одна из набивочных пружин поршня. Предложили "зачистить рабочие поверхности, поршень и набивочные кольца сточить до зазора, трещину по концам высверлить и вставить чугунные пробки, заводу приступить к изготовлению нового ЦНД. Старый цилиндр скрепить скобами на болтах, испытать давлением полного хода, в плавании использовать его на полных ходах не более 6 часов. Крейсер снабдить глухими фланцами, на случай отключения цилиндра".
6 октября "Олег" под флагом контр-адмирала Паренаго вышел для испытания машин и механизмов. Осадка носом составила 6,91 м, кормой - 6,7 м, перегрузка - около 800 т. При проведении прогрессивных испытаний, по достижению 127 оборотов пробило прокладку крышки левого ЦВД. Сбавили ход и продолжили испытание маневренности главных регуляторов, которая оказалась совершенно неудовлетворительной. Представитель завода прервал дальнейшие испытания и предложил на замену регуляторы другой системы, которые уже изготавливались на заводе. При работе машин применялась обильная смазка дорогим импортным деревянным маслом, хотя по контракту полагалось использование более дешевого, минерального. В топках сжигались кардиф и брикет № 2. После испытаний был произведен осмотр ЦНД правой машины, изменений не обнаружили. Комиссия пришла к выводу, что брак в цилиндре произошел по вине производства, поэтому завод обязали изготовить новый за свой счет.
Флотское начальство торопилось "выпихнуть" крейсер в заграничное плавание вдогонку 2-й эскадры. Почти каждый день "Олег" посещал вице-адмирал Бирилев, подгоняя офицеров своими ядовитыми замечаниями. Остойчивость построенного корабля можно было определить в гавани, во время ремонта машин, однако возникали опасения, что это приведет к дальнейшей задержке. Поэтому Бирилев внушил управляющему Морским министерством "оригинальную" мысль: раз испытания проведены на "Богатыре", а "Олег" построен по его чертежам, то их можно не проводить, с чем вице-адмирал Авелан охотно согласился.
11 октября императорская чета в сопровождении королевы эллинов, генерал-адмирала, вице-адмиралов Авелана, Бирилева и Ломена прибыла на яхте "Александрия" проводить "Олег" в дальнее плавание. После осмотра корабля царь обратился к собранной на шканцах команде с пожеланиями счастливого плавания. На следующий день, приняв комиссию от механического отдела МТК из 11 человек, крейсер вышел на мерную милю. На первом пробеге при 108 оборотах развили скорость 17,86 уз. На втором при скорости 19,7 уз. положили руль лево на борт, поворот на 16 румбов был осуществлен за 2 мин 32с с креном 4° на наружный борт. На третьем при 135 оборотах дали полный задний ход обеим машинам - крейсер остановился через 2 мин 15 с, пройдя 0,4 мили. На следующем пробеге совершили полную циркуляцию за 3 мин 5 с, на последнем достигли скорости 20,6 уз. при 133 об/мин. На малом ходу перевели управление рулем на электромотор. На этом испытания закончились, не были определены расход угля и полная мощность машин. Для достижения 23-уз. скорости при переуглублении в 0,61 м корабельные машины должны были развить мощность 21 250 инд. л.с. (по расчету).
Через два дня после испытаний Бирилев выпроводил крейсер из Кронштадта в Биорке, где провели отстрел минных аппаратов (9 выстрелов), стрельбы из револьверов, винтовок и пулеметов, что было оформлено актом на списание использованных боеприпасов; заодно списали 30 металлических ложек и 22 кружки, утраченные мастеровыми за время нахождения на корабельной порции. Так и не окончив полный курс испытаний, "Олег" вышел в Либаву - место сбора отряда. Во время перехода командир форсировал боевую подготовку - тренировки и учения следовали одни за другими.