Уехать из Томска ему удалось только поздней весной. Опять потянулась бесконечная дорога, ещё более пустынная, чем прежде. Шли месяцы. Новое лето сменилось новой осенью, настала зима, а Штеллер всё скакал и скакал. В январе 1739 года он прибыл в Енисейск. В Енисейске Штеллер встретился с естествоиспытателем Миллером, тоже участником Беринговой экспедиции. Миллер приехал в Енисейск по поручению Беринга для закупки разных материалов, необходимых экспедиции. Он обрадовался Штеллеру, потому что мог поручить ему сопровождать обоз, отправляемый на Камчатку. Сам Миллер должен был ещё остаться в Енисейске.

С обозом Штеллер поехал ещё медленнее. Немало прошло времени, прежде чем он прибыл в Иркутск. Тут его ждала новая задержка. Иркутское начальство должно было ему выдать денег на дальнейшее путешествие. В казначействе ему заявили, что деньги ещё не присланы из Петербурга и что придётся подождать.

Пять месяцев просидел Штеллер вместе с обозом в Иркутске, не имея ни копейки на обед, питаясь хлебом и квасом. Наконец приехал сильно запоздавший Миллер и сразу понял, в чём дело. Он невзначай, здороваясь с главным казначеем, сунул ему за рукав двадцать рублей, и деньги Штеллеру были немедленно выданы. Миллер сам взялся сопровождать обоз дальше, и Штеллер ускакал вперёд один.

Наступила уже зима, когда он добрался до реки Лены. Лена замёрзла и превратилась в широчайшую снежную дорогу, тянущуюся на несколько тысяч вёрст. Всю зиму Штеллер мчался в санях по Лене и в мае 1740 года прибыл в Якутск. Здесь он не мог задержаться. Ему нужно было попасть в Охотск до осени.

В те времена между Якутском и Охотском существовали только лесные тропинки. Штеллер сел верхом на оленя и в сопровождении проводника-якута тронулся в путь.

Всё лето ехали они по дремучей тайге. Ночами спали по очереди — три часа якут, три часа Штеллер, — потому что боялись нападения медведей. За три месяца только один раз встретили людей, когда набрели на кочевье тунгусов. Утром 20 августа 1740 года с гор увидели море. А вечером въехали в Охотск.

В бухте стояли два только что построенных корабля. Их поспешно грузили. Они готовились к выходу в море.

Приехав, Штеллер явился к Берингу. Они не понравились друг другу сразу. Мало того, они сразу поссорились. Мы не знаем, в чём там было дело, нам известно только, что уже через несколько дней после приезда Штеллер отправил в сенат донесение, в котором писал: «Во всём принят не так, как по моему характеру принять надлежало, но яко простой солдат, и за подлого от него, Беринга, и от прочих признаван был, и ни к какому совету я им, Берингом, призыван был».

Трудно теперь судить, много ли правды в этом донесении. Скорее всего немного. Мы знаем, что Беринг был демократичен, благожелателен и мягок в своих отношениях с подчинёнными. Когда к нему прислали разжалованного в матросы Овцына, обвиняемого в государственных преступлениях, он не без риска для себя обошёлся с ним на редкость дружелюбно, и матрос Овцын жил с офицерами и исполнял в экспедиции офицерские обязанности. С какой же стати стал бы Беринг унижать адъюнкта Академии наук, которого он видел впервые в жизни? И если между ними при первом же свидании возникла ссора, то естественнее предположить, что виноват в ней был Штеллер. Слишком много у нас есть свидетельств его неуживчивости, нетерпимости и своевольства.

Взаимная неприязнь, возникшая между ними при первом свидании, сохранилась надолго. Впрочем, Беринг был в своей неприязни к Штеллеру очень сдержан, избегал открытой вражды и сносил его совершенно непозволительные выходки с поражающею терпеливостью. Зато Штеллер был нетерпелив и нетерпим. Он оставил нам записки о своём путешествии, в которых страстно, не стесняясь в выражениях, возмущается каждым шагом Беринга, каждым его решением. Надо отдать справедливость и Штеллеру: в его резких суждениях не было почти ничего личного, они продиктованы интересами науки. Всякое пренебрежение к интересам науки он истолковывает как измену, как преступление. В отдельных своих суждениях он часто прав. Не прав он в основном, главном: без Беринга, без его осторожности, мелочной предусмотрительности, практичности, уступчивости, терпеливости ничего из того, что достигла экспедиция, не было бы достигнуто.

Этим двум людям — Берингу и Штеллеру — суждено было стать спутниками в великом трагическом плаванье значительно расширившем наши знания о мире. Но до чего же не сходны были эти два человека!

Беринг был стар и тучен, всякое движение давалось ему с трудом, полная лишений жизнь на краю света была для него тяжела. Штеллер был молод и обладал исключительным здоровьем, в самых тяжких условиях чувствовал себя прекрасно, любые лишения переносил с лёгкостью, не замечая их.

Беринг был человек не слишком образованный, чуждый интересам чистой науки, проявлявший внимание только к тем знаниям и открытиям, которые относились к наиболее близкой ему области — мореплаванию. Штеллер был, безусловно, одним из образованнейших людей своего времени, жадно интересовался вопросами географии, физики, геологии, этнографии, медицины, языкознания, не говоря уже о его основном предмете — ботанике. Не существовало такой длинной дороги, таких тяжёлых испытаний, которые могли бы остановить его, если он надеялся собрать какие-нибудь новые научные сведения.

Беринг был человек государственный, всю жизнь проведший на службе России, понимавший значение своей деятельности для русского государства. Мало того, он был человеком определённой партии, сторонником сподвижников Петра, он крепко связав с ними свою судьбу, разделял их взгляды и проводил эти взгляды в жизнь. Штеллер, напротив, был представителем тех безродных авантюристов, готовых служить любой стране и любой власти, которыми так богат восемнадцатый век. Только искренняя и самоотверженная преданность науке скрашивала его абсолютную беспринципность.

Беринг был человек долга, на нём всегда тяжким грузом лежало сознание ответственности за порученное дело, за подчинённых ему людей, за государственные средства, которыми он распоряжался. Штеллер чувствовал себя совершенно свободным от каких-либо обязательств, отдался науке только из своей неукротимой любознательности и нисколько не считал зазорным писать доносы на своих товарищей по путешествию. Если с ним в чём-либо не соглашались, он угрожал жаловаться начальству и исполнял свои угрозы; в архивах сохранилось немало его доносов, несправедливых, вызванных минутной вспышкой гнева. Как резко отличаются от них донесения Беринга, который всегда писал о своих сотрудниках только хорошее и старательно подчёркивал их заслуги!

Они были во всём различны, но плаванье в Америку они совершили вместе, и за результаты этого плаванья мы должны быть благодарны им обоим.

Только 8 сентября «Пётр» и «Павел» вышли, наконец, из Охотска в море. Была уже осень, начинались бури, и Беринг, разумеется, в такое время года не собирался плыть в Америку. Но ему необходимо было покинуть Охотск, чтобы избежать гнева начальства, уже окончательно выведенного из терпения. Он шёл на Камчатку, чтобы будущим летом с Камчатки начать своё плаванье. Он пересёк Охотское море и прежде всего зашёл в Большерецк — на западном побережье Камчатки. Там он оставил нескольких человек, в том числе и Штеллера. Сам он собирался на своих кораблях немедленно идти вокруг южной оконечности Камчатки к восточному побережью и там зимовать.

Штеллеру он приказал добираться до него по суше к весне будущего года. Видимо, они оба стремились к разлуке.

На восточном побережье Камчатки Беринг на этот раз привёл свои корабли в Авачинскую бухту — одну из лучших гаваней мира. Ограждённая со всех сторон горами, соединённая узким проливом с Тихим океаном, эта бухта может вместить в своих спокойных глубоких водах целый флот. Беринг слышал о замечательной Авачинской бухте ещё во время первого своего плаванья. Весной 1740 года он отправил туда несколько плотников, которые построили на её берегу пять изб, три казармы и три амбара. «Пётр» и «Павел» вошли в Авачинскую бухту 6 октября. С этого дня посёлок на берегу бухты стал называться Петропавловском.