И тут перед Невельским встала дилемма. Главная задача была решена, а времени оставалась еще много. Если бы теперь появились посланцы Муравьева, то, вероятно, удалось бы освободиться от обязанности исследовать залив великого князя Константина и всю эту часть побережья Охотского моря. В этом случае он смог бы вторично исследовать Южный пролив, но теперь уже на "Байкале", а не на шлюпках, обогнуть таким образом весь Сахалин и доказать всему миру, что Сахалин — остров и что пролив между ним и материком вполне проходим морскими судами. Но никто, однако, не показывался вблизи "Байкала". Приказание генерал-губернатора было необходимо исполнить. Пришлось отправиться для проведения предписанных исследований.
На этом пути и был встречен Орлов, разыскивающий "Байкал". Только сейчас Невельской узнал, что к нему направлен Корсаков с долгожданными инструкциями. Из письма Муравьева, посланного из Якутска (его тоже доставил Орлов) стало ясно, что генерал-губернатор может оказаться в Охотском порту на обратном пути с Камчатки. Но встреча с Орловым произошла в тот момент, когда все работы были уже завершены, а "Байкал" направился в Аян, где должны были остаться находившиеся на его борту алеуты. Неожиданная встреча с правителем края как бы венчала триумф осуществившихся замыслов.
Из Аяна Муравьев со всеми документами о своем путешествии и об исследованиях Невельского не ехал, а буквально мчался, словно на крыльях летел в Якутск. Даже трудный переход через хребет Джугджур показался легким. Планы были великолепны и казались близкими к осуществлению: перенести порт в Петропавловск, начать Широкое освоение далекой Камчатки, открыть плавание по Амуру, организовать экспедицию по исследованию Амурского края, основать там поселения, возвратить стране исконно русские земли по Амуру. Неизбежные дорожные осложнения на Аянском тракте не задержали надолго путешественников, и 22 сентября губернаторский караван прибыл в Якутск. Невельской же благополучно доставил транспорт в Охотск, сдал его местному начальству с командой, а сам с офицерами отправился в долгое путешествие по суше в столицу. Прибыв в Якутск 3 октября, он застал тут еще Муравьева со свитой, ревизовавшего область. В ожидании зимнего пути генерал-губернатор прожил тут более месяца, не только в деталях вникнув в управление областью, но и составив описание Якутского казачьего городового полка.
Но сразу после своего приезда в Якутск, воспользовавшись тем, что еще можно было проехать летником, он срочно направил с докладами в Петербург М.С. Корсакова. Муравьев писал по этому поводу Меншикову 28 сентября: "Встретившись с Невельским в порте Аяна, я получил от него 1 сентября рапорт об исполнении возложенного на него поручения и запечатанные донесения для доставления к Вашей светлости. Важность дела не дозволяет мне отправить этих донесений с почтою; и я поспешаю… командировать для доставления оных к Вашей светлости состоящего при мне для особых поручений капитана Корсакова. Из рапорта Невельского и карты, ко мне представленной, я вижу, что Невельской превзошел все наши ожидания и исполнил данные ему инструкции с тою полнотою, точностию и самоотверженностию, которые только можно ожидать от глубокой, беспредельной преданности престолу и отечеству и от истинно-русского смысла. Сделанные Невельским открытия неоцененны для России; множество предшествовавших экспедиций в эти страны могли достигать европейской славы, но ни одна не достигла отечественной пользы, по крайней мере в той степени, как исполнил это Невельской".
И еще о славном мореплавателе: "Приемлю сказать здесь несколько слов о Невельском: мне много случалось ходить на судах военного нашего флота и видеть много смелых и дельных офицеров, но Невельской превосходит в этом отношении все мои сравнения…"
Отважный капитан-лейтенант, осуществив свою заветную мечту, сделал первый и самый важный шаг к возвращению Приамурья. Это высоко оценил Муравьев. Он отлично понимал, какие перспективы открывали перед Россией и перед ним — представителем высшей власти в этом крае — исследования Невельского. И он немедленно принялся за осуществление возникших планов. Муравьев со свитой уехал тотчас же по наступлении зимнего пути. 20 ноября он был уже в Иркутске. Невельской и его офицеры на некоторое время еще задержались в Якутске, заканчивая окончательные отчеты и составляя подробные карты путешествия. В столицу Восточной Сибири они прибыли несколько позже. Теперь можно было отправляться в Петербург, отстаивать свои открытия и оправдываться перед царем за превышение полномочий.