Лейтенант Лазарев прибыл в Архангельск 19 апреля с лейтенантом Корсаковым и Барановым. Ему дан был конфискованный английский бриг «Кетти», обращенный в транспорт, который, по назначении в эту экспедицию, назван был «Новая Земля». Приведение этого довольно старого судна в состояние выдержать предстоящую ему тяжкую службу стоило многих трудов. По вскрытии реки Двины приведено оно было из Лапоминской гавани, для окончательного вооружения, к Адмиралтейству. 19 мая прибыл из С. – Петербурга мичман Кюхельбекер, с инструментами, которые при отъезде Лазарева еще не были готовы, а к 9 июня бриг «Новая Земля» был совершенно готов к отправлению в море. Он был снабжен всеми нужными астрономическими и математическими инструментами, провизией на год, разными противоцинготными средствами, теплой одеждой и обувью и всякого рода орудиями для ловли зверей, птиц и рыб. На случай зимовки были приготовлены две разборные избы, но теснота судна не позволила Лазареву взять с собой более одной. Сверх упомянутых уже офицеров, находились на его бриге штурман Харлов 1-й, штаб-лекарь Братановский, и 44 человека нижних чинов служителей. Назначены были еще горный чиновник и рисовальщик, но они не застали уже в Архангельске бриг «Новая Земля», отправившийся в море 10 июня.
14 числа лейтенант Лазарев подошел к острову Моржовец и от него взял курс прямо к Канину Носу, который миновал 16 июня, не встретив на пути ничего, кроме нескольких гряд берегового льда. По счастливому случаю избежал он всех опасностей, которыми усеяна эта часть моря, и, как кажется, не попал даже ни на одну из малых глубин, поскольку о них не упоминает. Это побудило его рекомендовать путь восточной половиной моря всем плывущим судам из Архангельска в Северный океан. Однако же преопасные Северные Кошки и жестокие, неправильные течения, конечно, навсегда удержат их при вернейшем и нисколько не более продолжительном западном пути, на котором и льдов менее встречается, чем на восточном. В 1821 году мы последовали совету Лазарева и едва избежали совершенного корабле-крушения.
При первом вступлении в Северный океан встретили Лазарева льды. Намерение его было плыть прямо к Маточкину Шару, так как он полагал, что продолжавшиеся всю весну северные ветры должны были очистить ото льдов севернейшие берега Новой Земли; но, видя, что по мере удаления к северу возрастает количество и плотность льдов, решился он идти к южной оконечности Новой Земли, но и с этой стороны поставили ему льды необоримые препятствия. 1 июля, убедившись, что весь южный берег до мыса Бритвина окружен непроходимым льдом, решился он спуститься к острову Колгуев, который и увидел в тот же день. Около этого времени стала появляться в экипаже брига болезнь, бывшая впоследствии одной из главных причин худого успеха экспедиции.