В результате подробного изучения вопроса комиссия предложила исследовать Северный морской путь с помощью двух ледоколов.
Рассмотрев многие варианты экспедиционных судов, комиссия остановилась на предложении Невского судостроительного и механического завода в Петербурге создать два однотипных ледокольных транспорта. После одобрения в высших инстанциях проекта исследования Северного Ледовитого океана, предложенного комиссией, с этим заводом морское ведомство и заключило контракт на постройку двух ледокольных пароходов. Их назвали «Таймыр» и «Вайгач». На должности командиров строившихся судов решили пригласить морских офицеров с опытом полярного плавания. Выбор пал на участников экспедиции Толля, капитанов 2 ранга Ф. А. Матисена и А. В. Колчака. 9 мая 1908 года Николай II подписал приказ о назначении Матисена командиром транспорта «Таймыр», Колчака – «Вайгач».
Первоначально предполагалось обследовать часть побережья и прилегающие воды Северного Ледовитого океана от Берингова пролива до устья Лены, а затем, в зависимости от состояния льдов, продолжать гидрографическую опись до ранее обследованных районов. Весной 1909 года «Таймыр» и «Вайгач» были спущены на воду. Они имели стальные корпуса с усиленным креплением и утолщенной обшивкой, с обводами подводной части, типичными для ледоколов. Все лето и начало осени на них велись достроечные работы. В итоге морское ведомство получило два относительно небольших, но вполне современных судна, пригодных для плавания в Арктике.
Наконец пришло время отплытия. Колчака провожали жена и отец. Софья Федоровна недавно сообщила мужу, что у них снова будет ребенок. Василий Иванович, одетый в форменное пальто с генерал-майорскими погонами, бодрился. Только при прощании, обнимая сына, старый генерал прослезился.
Приняв в Кронштадте уголь, воду и дополнительное необходимое снаряжение, «Таймыр» и «Вайгач» 28 октября 1909 года вышли в море. На борту каждого судна находились: 6 офицеров, врач и около 35 человек команды из матросов-добровольцев военного флота. Из-за незнания ледовой обстановки и навигационно-гидрографических условий в арктических морях организаторы экспедиции приняли решение перегонять свои новые и не испытанные еще во льдах транспортные ледоколы южным путем, через Суэцкий канал.
До Алжира суда шли три месяца, посетив пять портов. Еще в Северном море во время шторма кочегары «Таймыра» спустили воду из котлов, отчего просели топки. Авария потребовала двухмесячного ремонта в Гавре. Морское командование, не посчитавшееся с судоводительским опытом и авторитетом командира судна Ф. А. Матисена, отозвало его в Петербург. Командование ледокольным транспортом «Таймыр» принял в Порт-Саиде капитан 2 ранга А. А. Макалинский. Колчак впервые встретился с ним в Морском Генеральном штабе весной 1908 года, когда Макалинский начинал службу на штаб-офицерской должности.
Дальнейшее плавание экспедиционных судов из-за неисправности котлов еще более затянулось, и во Владивосток – базу экспедиции – «Таймыр» и «Вайгач» прибыли только 3 июля 1910 года, на два месяца позже намеченного срока. Несмотря на эти неудачи и некоторые трудности длительного похода (штормы, тропическая жара), экипажи судов оправдали доверие командования. Офицеры проделали на переходе и большую научную работу, результатом которой явились объемистые, к сожалению, несохранившиеся журналы с записями гидрометеорологических, океанографических, аэрологических, биохимических и других наблюдений.
Проводившийся во Владивостоке ремонт котлов занял полтора месяца. Значительная часть забот легла на Александра Васильевича, поскольку командир «Таймыра» Макалинский в середине июня был отозван Главным морским штабом в Петербург. 9 августа прибыли начальник экспедиции полковник Корпуса флотских штурманов И. С. Сергеев и старший лейтенант Б. В. Давыдов (вместо Макалинского).
17 августа 1910 года экспедиция вышла в море. На нее возлагались следующие основные задачи: морская опись берегов Северного Ледовитого океана к западу от мыса Дежнева, а также близлежащих островов, определение астрономических пунктов, промер, гидрометеорологические, магнитные, ледовые наблюдения и гидрологические разрезы, измерение элементов морских течений и наблюдения над уровнем моря, сбор зоологических и биологических коллекций и материалов для составления лоций, сооружение навигационных знаков. В бухтах, устьях рек и местах якорных стоянок съемочно-промерные работы надлежало выполнять более подробно.
Миновав Берингов пролив, участники экспедиции приступили к определению координат знака, сооруженного ими на северном берегу мыса Дежнева. Пройдя 30 миль к западу от селения Уэлен, суда встретили лед; температура воздуха понизилась ночью до семи градусов мороза, начался снегопад, видимость значительно ухудшилась. Опытный гидрограф-полярник, но нерешительный в своих командирских действиях И. С. Сергеев решил прекратить работы, и 21 сентября экспедиция повернула назад. На обратном пути суда захватил шторм, и им пришлось укрываться в бухтах. Со 2 по 10 октября они простояли в Петропавловске-Камчатском и 20 октября вернулись во Владивосток.
Так закончилась первая кампания Гидрографической экспедиции Северного Ледовитого океана. Результаты ее работ были не особенно велики: планшеты описи бухт Петра и Павла, по которым позже были внесены заметные коррективы в изданные навигационные карты, а также данные проведенных наблюдений над течениями и первая коллекция донной морской фауны. Однако они оценивались весьма положительно, поскольку знаменовали собой начало изучения Северного морского пути.
14 декабря Колчак получил телеграмму от морского министра и начальника Морского Генерального штаба с приказанием сдать командование судном и дела по экспедиции и прибыть в Петербург для продолжения ответственной работы в Морском Генштабе. Сборы были недолги. Сдав «Вайгач» своему помощнику, лейтенанту Н. А. Гельшерту (вскоре командиром «Вайгача» был назначен капитан-лейтенант П. Н. Новопашенный), и распрощавшись со своими коллегами по судну и экспедиции, Колчак поездом выехал в Петербург.
Дома Александра Васильевича ожидало радостное известие. Спустя четыре месяца после его ухода в море на свет появился сын. Ростиславу только что исполнилось десять месяцев, но в нем что-то уже угадывалось от отца. Софья Федоровна не чаяла в нем души. Она похорошела и даже как бы помолодела.
На другой день Колчак предстал перед начальником Морского Генерального штаба, князем А. А. Ливеном. Князь поздравил Колчака с успешным плаванием и тут же перешел к делу. Недолгая беседа закончилась для капитана 2 ранга неожиданным и приятным сюрпризом: ему предлагалась должность начальника 1-й оперативной части штаба. Справившись с волнением и выразив благодарность за оказанную высокую честь, Колчак принял предложение. Начальник штаба предоставил ему недельный отпуск на устройство домашних дел, пожелал успехов на новой ответственной должности, посоветовав зайти в Главное гидрографическое управление, где ожидал его Андрей Ипполитович Вилькицкий, долгие годы возглавлявший гидрографические работы от устья Печоры до Енисея, в Енисейском заливе и Обской губе.
Через несколько минут Александр Васильевич был уже там. Генерал-лейтенант корпуса флотских штурманов, известный гидрограф-геодезист, исследователь Арктики Андрей Ипполитович Вилькицкий принял бывшего командира «Вайгача» радушно. Начальника управления интересовало все о Гидрографической экспедиции Северного Ледовитого океана, о делах которой он пока знал только по телеграфным сообщениям из Владивостока. Сергеева ожидали в Петербурге не раньше середины января. Он расспрашивал о личном составе, особенно о деловых качествах офицеров, о результатах гидрографических работ, о мореходных достоинствах и недостатках «Вайгача» и «Таймыра», выявленных в длительных плаваниях, о состоянии судовых котлов после ремонта и пригодности транспортов к работе во льдах.