Экспедиция вышла из Петербурга в июне 1900 г. на судне «Заря», прошла Ледовитым океаном через Карское море и зазимовала на Таймырском полуострове. Следующая зимовка была проведена на острове Котельном, после чего весной 1902 г. экспедиция обследовала группу Новосибирских островов. В это время барон Толль вместе с астрономом Зеебергом отправился на нартах к острову Беннетта, откуда им уже не суждено было вернуться.
Другие участники экспедиции в декабре 1902 г. возвратились в Петербург, однако там было решено снарядить новую весьма рискованную экспедицию по спасению барона Толля, которую вызвался возглавить сам Колчак. Восемь месяцев длились поиски, но они лишь констатировали гибель смелых исследователей. Полярный поход сквозь тысячемильное ледяное крошево, через шесть необитаемых островов протекал в невероятно трудных условиях. Как докладывал позднее Колчак, «тяжелые нарты, а особенно вельбот, ограниченный корм для собак и сравнительно теплое время, заставлявшее нас находиться в пути только в ночные часы, когда становилось холоднее, обусловили невозможность делать переходы больше 5‑ти часов в сутки – собаки отказывались идти больше, несмотря на то, что мы все шли в лямках. Торос, местами очень серьезный для обыкновенных нарт, заставлял нас постоянно останавливаться, рубить дорогу для вельбота и общими силами перетаскивать 36‑пудовую шлюпку через хаотически нагроможденные холмы ледяных глыб и обломков».
Однажды Колчак чуть не утонул, провалившись в ледяную воду и потеряв от температурного шока сознание. Боцман Бегичев, вытянувший Колчака из воды за голову, вспоминал: «Мы сняли с Колчака сапоги и всю одежду, потом я снял с себя егерское белье и стал надевать на Колчака. Оказался он еще живой. Я закурил трубку, дал ему в рот. Он пришел в себя». Затем Бегичев специально выбирал путь с крутыми подъемами, чтобы Колчак скорее согрелся (подробнее об экспедиции по спасению барона Толля см.: Вокруг света. 1991. № 1–2).
Позднее на картах появился остров Колчак (76° с.ш., 97° в.д.), названный в честь смелого исследователя, однако совсем ненадолго: революция мстительно лишила своего поверженного врага такой высокой чести, и на нынешних картах остров Колчак обозначается островом Расторгуева…
Многолетнее пребывание Колчака в условиях Крайнего Севера сильно подорвало его здоровье, вскоре у него появились признаки суставного ревматизма, протекавшего в очень тяжелой форме. Однако отдыхать не пришлось. В Якутске, где Колчак находился после завершения экспедиции, его застала новость о начале Русско-японской войны. Он просится на Дальний Восток и получает приказание ехать в Порт-Артур. За три дня до отправления из Иркутска Колчак выполняет свое давнее желание, которое никак не удавалось осуществить, – венчается со своей невестой Софьей Федоровной Омировой (1876–1956).