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