Витте был упрям и, не желая отступать от своей идеи, а лишь видоизменив ее, внес на рассмотрение в Государственный совет. «В видах правильного развития нашей торговли на Севере и ослабления ее зависимости от иностранных купцов, – утверждал он, – следует безотлагательно приступить к устройству на

Мурманском берегу удобного для стоянки судов коммерческого порта, который вместе с тем служил бы и административным центром». По мнению министра, с появлением портовой инфраструктуры на Мурман потянутся желающие поселиться на новом месте, что даст толчок к дальнейшему усилению там русского присутствия. Правительство же возьмет на себя «инициативу в деле сооружения за казенный счет в Екатерининской гавани частных домов, которые на известных льготных условиях по пониженной стоимости передавались бы в собственность благонадежным лицам из числа русских подданных». Предполагалось перевести из Колы в новый порт все административные учреждения, больницу, школу и почту.

Государственный совет отнесся к этой инициативе благосклонно и 8 апреля 1896 г. одобрил предложение Витте. По распоряжению Николая II из казны на строительство порта выделялось 400 тысяч рублей.

Летом 1896 г. в Екатерининской гавани началась подготовка к возведению портовых сооружений, жилых и административных зданий будущего города. Для проведения осушительных работ и планировки местности наняли группу норвежских рабочих под началом инженера Ульсена.

Берега гавани изобиловали отвесными скалами. В 300–400 метрах от моря подрядчикам удалось найти и застроить несколько ровных площадок.

Для удобства подхода судов, их загрузки и разгрузки береговую часть на протяжении нескольких сотен метров выровняли и облицевали камнем, а поверху устроили набережную. Крупнотоннажные и глубокосидящие корабли швартовались у специальной пристани. Суда снабжались водой по 200-метровому водопроводу. Пристань соединялась с товарными складами, пожарным обозом и бассейном, где хранили пресную воду, железнодорожными ветками, отходящими от магистрали, протяженностью 1,5 километра, проложенной вдоль всего поселения. Параллельно пролегало почти 600-метровое шоссе. При закладке фундаментов под здания, устройстве железной дороги, шоссе, набережной и водопровода пришлось взорвать динамитом 12 тысяч кубометров скальных пород – это делали норвежские подрядчики. Всего в 1898 г. на работы по строительству порта и города ежедневно выходили до 200 русских и около 50 норвежских рабочих.

Через три года – в рекордно короткий срок – на берегу затерянной среди скал и тундры северной бухты появился новый русский город. В феврале 1898 г. последовало высочайшее повеление о перенесении уездного управления из Колы в Екатерининскую гавань.

24 июня 1899 г. в присутствии великого князя Владимира Александровича, многочисленных русских и иностранных гостей, журналистов, ученых, промышленников состоялось официальное открытие города. На праздник специально прибыли крейсер «Светлана», военный гидрографический пароход «Пахтусов», крупнейшие пароходы Товарищества Архангельско-Мурманского срочного пароходства «Император Николай II», «Сергей Витте», «Королева Ольга Константиновна», «Чижов» и «Трифон Печенгский», норвежский броненосец «Торденшельд», пароход Мурманской научно-промысловой экспедиции «Андрей Первозванный».

Перед собравшимися огласили «мнение Государственного совета» от 7 июня 1899 г. о присвоении «городскому поселению и порту при Екатерининской гавани… названия “Александровск” и переименовании Кольского уезда в Александровский»