Еще до Завойко начальник Охотского порта Миницкий предпринял изыскания более удобного места для порта. Путь из Якутска к берегам Охотского моря намечался Фоминым в 1806 году по реке Лене и далее в Алдомский залив.
Благодаря своим связям Завойко получил от Российско-Американской компании разрешение действовать по своему усмотрению для подыскания нового места порту. Завойко остановил свое внимание на заливе Аян и в мае 1842 года на китобойном вельботе отправился в путь. Он взял с собой Орлова, "бывшего штурмана", тогда еще ссыльнопоселенца. По всеобщим отзывам, Орлов был опытным путешественником и мастером своего дела; Завойко остался доволен своим выбором.
Но запала у Завойко хватило всего на несколько дней пути, за которые пройдено было 120 верст. Экскурсия оказалась малоприятной. Ночевать приходилось на пустынном берегу, среди еще не стаявших снегов. Намокшие и продрогшие за день путешественники сушились у костра из сырых, дымящих ветвей. А тут еще в один прекрасный день неожиданно подул с моря ветер, и понесло на сушу целые ледяные поля, которые едва не раздавили вельбот. С трудом удалось вытащить его на берег.
Между тем близилось время прихода кораблей с Аляски и островов. Завойко очень кстати вспомнил, что ему следовало быть на месте для принятия грузов. Поручив все дальнейшие труды и заботы Орлову, лейтенант отобрал себе проводников понадежнее и берегом пустился в обратный путь на Охотск.
Орлов же довел дело до конца и, добравшись до Аяна, составил карту Аянского залива, а по пути туда - эскизную карту побережья. Обратный путь он совершил на присланном за ним бриге компании.
На следующий год Завойко, памятуя трудности прошлого путешествия, не поехал с Орловым, а отправил его с тунгусом Афанасием не на вельботе, а на простой рыбацкой лодке.
Орлов и Афанасий довольно быстро убедились, что лодка не годится для плавания по бурному весеннему морю, среди льдов. Они, однако, успели добраться на ней до реки Ульи.
Плыть дальше было и трудно и опасно на перегруженной и тесной лодке. Орлов и Афанасий сделали длительный привал. В несколько дней они перестроили лодку, увеличив ее грузоподъемность и улучшив мореходные качества.
Афанасий проявил большую ловкость и сметливость в этой работе. 10 мая путники уже могли следовать дальше. Путешествие было тяжелым. Днем холод, дождь, ветер, борьба с волнами, течением и льдинами. Ночью приходилось спать поочередно. Наступило время весенних медвежьих свадеб. Медведей было столько, что по ночам лес гудел от их рева и драк.
На десятый день пришли к реке Алдоме и встретили здесь тунгусов, из которых двое согласились следовать в помощь Орлову и Афанасию до самого Аянского залива. 25 мая обогнули высокий скалистый мыс и увидели Аянский залив. На окружавших его горах лежали тучи, залив был покрыт льдом. Путники вытащили лодку на берег, сами же укрылись от непогоды под скалами у озера.