В 1895-1899 гг. - в дальних заграничных плаваниях на крейсерах "Рюрик" и "Крейсер". Во время плаваний в водах Тихого океана (в основном китайских и корейских) соприкоснулся с тем, что сыграло впоследствии громадную роль в его жизни, - с миром Востока и со стихией северных морей. Пытался самостоятельно изучить китайский язык. Начал заниматься наукой (океанографией, гидрологией, картами течений у берегов Кореи). Готовил себя к южнополярной экспедиции, мечтал продолжить работы Ф.Ф. Беллинсгаузена и М.П. Лазарева, дойти до Южного полюса. К этому времени прекрасно владел тремя европейскими языками, хорошо знал лоции всех морей Земли.
Приглашенный бароном Э.В. Толлем в Русскую полярную экспедицию (РПЭ), смотрел на нее как на пролог будущей Русской антарктической экспедиции. В ходе подготовки к РПЭ изучил магнитологию в Павловской магнитной обсерватории; практиковался в Норвегии у Фритьофа Нансена.
В 1900-1902 гг. прошел с "Зарей" (бывшим норвежским китобойным судном) путь по арктическим морям с двумя зимовками (каждая - по одиннадцать месяцев): у берегов Таймыра и у острова Котельный. Во время зимовок совершал дальние - до 500 верст - поездки на собачьих нартах и на лыжах, определял астропункты, вел маршрутную съемку и барометрическое нивелирование. На одном таком маршруте (вдвоем с Толлем) девять дней пришлось на стоянки из-за пурги и четыре - на безуспешное ожесточенное раскапывание снега в поисках ранее оставленного склада.
Исполнял должности гидролога и второго магнитолога. Толль отметил, что Колчак "не только лучший офицер, но он также любовно предан своей гидрологии"9 и "эта научная работа выполнялась им с большой энергией, несмотря на трудность соединить обязанности морского офицера с деятельностью ученого"10. Под руководством Колчака во время плавания проводились комплексные гидрологические исследования, по возможности ежесуточные. Он промерял глубины, выходил в разведку на паровом катере или шлюпке, наблюдал за состоянием льдов, контролировал ежечасный отсчет прилива на зимовке. После его съемок и описей береговая линия западного Таймыра и соседних островов приобрела совершенно новые очертания на картах; один из вновь открытых у берегов Таймыра островов Толль назвал именем Колчака. Поездка Колчака по льду к северу от острова Бельковский стала составной частью исследований, приведших к открытию круглогодичной заприпайной полыньи в этой части океана.
На первой зимовке выстроили специальный снежный домик на островке вблизи рейда "Зари": стены и потолок были укрыты парусиной, а керосиновая печь поддерживала температуру от нуля до плюс трех. Здесь Колчак вместе с Ф.Г. Зебергом вел магнитные наблюдения. С ним же на мысе Челюскин провел полные астрономические наблюдения для уточнения координат мыса.