По завершению празднества Матюшкину довелось наблюдать камлание шамана. «Странная его одежда, обвешанная ремнями с железными, медными и серебряными оконечностями, бубны в правой руке и лук в левой – всё, всё давало ему какой-то страшный вид, и он довольно был похож на чёрта в московском театре…» – не без юмора описывал юный мичман свои впечатления. Впавший в транс шаман отвечал на вопросы окружающих, и 21-летний Матюшкин тоже не удержался, спросил шамана: «Какую я люблю девушку?» Последовал ответ: «У твоей девушки глаза, как лазурь неба, а волосы, как слабый свет луны…»
Ответ больше всего поразил не Матюшкина, а местных обитателей. Мичман так описал их удивление в письме другу: «Женщины, которые, как и везде, любопытны, спрашивали у меня – что такое голубые глаза? И удивлялись, что у нас в России бывают не человеческие (т. е. не чёрные) глаза. По всей Сибири голубые глаза редки, и шаман также не имел о них понятия…»
Путь Матюшкина из Якутска но Колыму занял два месяца, август и сентябрь. Недавний лицеист потрясённо разглядывал и описывал в посланиях к столичным друзьям, как в самый жаркий месяц лета «в темных рытвинах меж холмов лежит вечный снег и лед». Только в октябре 1820 года, когда уже вовсю начиналась морозная якутская зима, он прибыл в городок Среднеколымск, лежащий в 400 верстах к югу от берегов Северного ледовитого океана.
Именно Среднеколымск должен был стать базой для экспедиции, и Матюшкин прибыл туда самым первым, на месяц опередив иных участников, чтобы подготовить всё необходимое. Местное начальство, как выяснилось сходу, не смотря на строгие приказы свыше, столичных гостей не ждало, понадеявшись, что посланцы далёкого Петербурга доберутся на Колыму ещё не скоро.
Бывшему лицеисту пришлось экстренно взяться за дело. Как позднее вспоминал начальник экспедиции Фердинанд Врангель: «Колымское начальство о нуждах экспедиции не озаботилось, не было припасено ни одной рыбы, не привезено ни одного бревна для постройки обсерваторий… Такие неисправности могли иметь самые пагубные последствия для наших действий, если бы Матюшкин, во время краткого своего здесь пребывания, похвальной своей деятельностью не успел многого поправить; узнав по прибытии своем о положении дел, он собрал и уложил тотчас половину нужной для экспедиции рыбной провизии, закупив ее у жителей Колымска и окрестностей. По распоряжению его и под его надзором, невзирая на сильные морозы, от которых топоры, как стекло, ломались, была выстроена башня с четырьмя окнами к четырем странам света для астрономических наблюдений…»
Мечтавший о дальних странствиях лицеист оказался хорошим организатором, не страшащимся неожиданных трудностей. Фактически, именно Матюшкин, оказавшись на Колыме, провёл все главные работы по подготовке экспедиции. Предстояло на собачьих упряжках объехать сотни вёрст заледенелых просторов, но снег и лёд на суше отличались от таковых поверх застывшего моря. Выяснилось, что обычные сани с деревянными полозьями хороши для тундры, но не годятся для дальних путешествий по солёному морскому льду. Как позднее в отчёте объяснял начальник экспедиции Врангель: «От выступающей морской воды остается на поверхности льда морской рассол, по которому деревянные полозья весьма тяжело скользят; для предотвращения такого неудобства привязываются под полозья китовые ребра, которые, будучи твёрже дерева, не всасывают в себя соли и не задерживают саней…»
Лучшими мастерами по изготовлению таких специальных полозьев из китовых ребер были чукчи. И хотя жестокие войны с ними ушли в прошлое, этот народ дальневосточного Севера всё ещё оставался малоизвестным и пугающим. Как вспоминали участники экспедиции, на Колыме местное начальство «рассказывало множество примеров коварства чукчей, описывая их людьми самыми опасными и жестокими».
Решили, что к таким опасным людям за китовыми рёбрами, без которых экспедиция становилась невозможной, отправится именно Матюшкин. Бывший лицеист в сопровождении одного казака и якута-переводчика выехал на реку Анюй, восточный приток Колымы. Раз в год там проводилась большая ярмарка, на которую приезжали старейшины чукчей, чтобы выменять русские товары на шкуры полярных животных.