Но тут произошли большие изменения в моих планах. В сентябре месяце я ушел на «Петропавловске» в Средиземное море, чтобы через Суэц пройти на Дальний Восток, и в сентябре прибыл в Пирей. Здесь я совершенно неожиданно для себя получил предложение барона Толля принять участие в организуемой Академией наук под его командованием северной полярной экспедиции. Мои работы и некоторые печатные труды обратили на себя внимание барона Толля. Ему нужно было трех морских офицеров, и из морских офицеров он выбрал меня. Я получил предложение через Академию наук участвовать в этой экспедиции».
В 1900 году Колчак уже лейтенант и поступает в распоряжение Российской Академии наук. Из Греции через Одессу он возвращается в Петербург и является к начальнику Русской полярной экспедиции барону Э. В. Толлю. Колчак начинает усиленно готовиться к плаванию — работал в Павловской магнитной обсерватории, в Главной физической обсерватории Петербурга, практиковался в Норвегии у друга Толля Ф. Нансена. Выйти в путь полярники собирались на специально оборудованном бывшем норвежском китобойном судне «Заря». В июне 1900 года их корабль отправляется в экспедицию.
С 1900 по 1902 год Колчак плавал на «Заре» по арктическим морям для обследования Ледовитого океана в районе Новосибирских островов и острова Беннетта. Сначала экспедиция прошла через Карское море и зазимовала в западной части Таймырского пролива, занимаясь изучением Таймырского полуострова. Следующая зимовка, также в одиннадцать месяцев, была на острове Котельном.
Колчак был гидрологом и вторым магнитологом экспедиции. На зимовках ему приходилось на собачьих нартах и лыжах делать броски до пятисот верст, чтобы определить астропункты, вести маршрутную съемку и барометрическое нивелирование. Однажды вместе с Толлем он завяз на маршруте: девять дней ушло на стоянки из-за пурги и четыре впустую раскапывали снег, так и не найдя ранее оставленный склад.
Барон Толль отмечал в своих записях, что Колчак «не только лучший офицер, но он также любовно предан своей гидрологии», «эта научная работа выполнялась им с большой энергией, несмотря на трудности в соединении обязанностей морского офицера с деятельностью ученого». Под руководством Колчака проводились комплексные гидрологические исследования. Он сам промерял глубины, выходил на разведку на катере, в шлюпке, наблюдал за состоянием льдов, на зимовках ежечасно контролировал приливы.
Один из островов и один мыс, открытые экспедицией у берегов Таймыра, Толль назвал именем Колчака не случайно. Например, где со спутниками, где в одиночку, Александр Васильевич впервые пересек остров Котельный, измерив высоты. Он проехал поперек земли Бунге. Путешествуя на запад и север от острова Бельковского, лейтенант послужил открытию круглогодичной заприпайной полыньи в этой части океана. Колчак открыл остров, названный именем Стрижева. В экспедицию он уходил женихом Софьи Омировой, и один из открытых им мысов острова Беннета лейтенант назвал именем своей будущей жены — Софии. Острову же и мысу имени самого Колчака при Советах долго везло, их коммунисты переименовали, спохватившись, лишь в конце двадцатых годов.
На первой зимовке Колчак вместе с другим магнитологом на мысе Челюскин провели полные астрономические наблюдения для уточнения координат. Много помогал Александр Васильевич и зоологу экспедиции, сопровождая его на береговых экскурсиях, собирая жуков, пауков, клещей, наблюдая птиц. Когда становилось туго, всем, невзирая на чины и звания, приходилось напрягаться наравне. Снимали судно с мелей, собирали плавник на растопку, уставали собаки — сами брались за лямки нарт. Матросы экспедиции охотнее всех начальников подчинялись Колчаку.
Весной 1902 года отчаянный барон Толль решился на рискованнейшее путешествие. На шхуне из-за состояния льдов не удалось пробиться к северу от Новосибирских островов, и он отважился вместе с магнитологом Ф. Г. Зеебергом и двумя каюрами двигаться туда пешком. Барон свято верил в еще не открытый северный материк — легендарную землю Санникова!
Остальным членам экспедиции, потому как кончались запасы продуктов, барон наказал пройти от острова Беннета южнее, провести исследования и вернуться в Петербург. Сначала Толль хотел взять с собой Колчака, но побоялся оставить «Зарю» без такого авторитетного офицера. Возможно, поэтому, без опоры на надежного напарника погибнет и сам барон. Толль вместе со спутниками собирался самостоятельно вернуться к устью Лены, для этого экспедиция должна была оставить для них в условленных местах продовольствие.
Подробно рассказывал и об этом чрезвычайке в Иркутске Александр Васильевич перед своим расстрелом:
«В 1902 году, весною, барон Толль ушел от нас с Зеебергом с тем, чтобы больше не возвратиться: он погиб во время перехода обратно с земли Беннета.
Лето мы использовали на попытку пробраться на север к земле Беннета, но это нам не удалось. Состояние льда было еще хуже. Когда мы проходили северную параллель Сибирских островов, нам встречались большие льды, которые не давали проникнуть дальше. С окончанием навигации мы пришли к устью Лены, и тогда к нам вышел старый пароход «Лена» и снял всю экспедицию с устья Тикси. Коллекции были перегружены на «Лену», и мы вернулись в Якутск, затем в Иркутск и в декабре месяце 1902 года прибыли в Петроград.
На заседании Академии наук было доложено общее положение работ экспедиции и о положении барона Толля. Его участь чрезвычайно встревожила Академию. Действительно, предприятие его было чрезвычайно рискованное. Шансов было очень мало, но барон Толль был человеком, верившим в свою звезду и в то, что ему все сойдет, и пошел на это предприятие. Академия была чрезвычайно встревожена, и тогда я на заседании поднял вопрос о том, что надо сейчас, немедленно, не откладывая ни одного дня, снаряжать новую экспедицию на землю Беннета для оказания помощи барону Толлю и его спутникам, и так как на «Заре» это сделать было невозможно (был декабрь, а весною надо было быть на Новосибирских островах, чтобы использовать лето) — «Заря» была вся разбита, — то нужно было оказать быструю и решительную помощь. Тогда я, подумавши и взвесивши все, что можно было сделать, предложил пробраться на землю Беннета и, если нужно, даже на поиски барона Толля на шлюпках».
Многие бывшие спутники Колчака отнеслись к его затее с сомнением:
— Такое же безумие, как и шаг барона Толля. Академия все же одобрила план Колчака и дала ему средства и полную свободу действий в этой спасательной операции. За свою первую полярную экспедицию Колчак был награжден орденом Св. Владимира IV степени. Боцман и рулевой старшина с «Зари» снова пошли с Колчаком на выручку пропавших полярников, а еще четверых товарищей Колчак нашел среди видавших виды тюленепромысловиков, хотя и пришлось за ними съездить на Мезень. Александр Васильевич сговорился по телеграфу с якутским ссыльным Олениным, чтобы тот подготовил ему на побережье собак и тяжелый китобойный вельбот с «Зари».
Когда команда Колчака в семнадцать человек прибыла в низовья реки Яны, вельбота там не оказалось. Лейтенант сел на оленьи нарты и направился за тысячу верст в Тикси, где стояла раздавленная льдами «Заря». Здесь он узнал, что вельбот тоже на оленях уже уехал к месту назначения. Колчак наконец догнал его в селении Казачьем на Яне.
В начале мая 1903 года спасатели отправились в путь. Вельбот везут на фантастическом поезде из двух нарт, запряженных собаками, а впереди и сзади еще десяток нарт. Каждую из них с людьми и припасами волокут тринадцать псов. Майские снег и лед рыхлы, нарты с тридцатипудовым вельботом то и дело проваливаются, больше идут ночами, когда подмораживает. Путь через громадные торосы приходится прорубать; когда выбиваются из сил собаки, нарты волокут люди.
Неудачно складывался поход. Когда пошли на Новосибирские острова, дважды сменили первоначальный план. Устремились по другому маршруту, побыстрее отделались от вспомогательной партии. Экономя продовольствие, скармливали собакам оленей, добытых охотой, а потом пришлось убивать и ненужную часть собак.