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