Из Петербурга Лаптевы выехали вместе. В Казани они получили такелаж для судов, в Иркутске — провиант, вещи для подарков жителям побережья Сибири и деньги. Харитон Лаптев потребовал, чтобы иркутская канцелярия подготовила на побережье оленей и собак на случай, если его отряду придется вести опись с суши, и переселила с устья Оленека в устья Анабара, Хатанги и Таймыры по две семьи промышленников, предписав им заняться заготовкой рыбы и постройкой жилищ на случай зимовки отряда в этих пунктах, одновременно Харитон Лаптев сообщил в канцелярию Туруханска о необходимости отправки летом 1739 года в устье реки Пясины провианта для его отряда.
В начале марта 1738 года Лаптевы прибыли в Усть-Кут, расположенный в верхнем течении Лены. Здесь для экспедиции строились небольшие речные суда. Весной, когда река вскрылась, на этих судах в Якутск были доставлены имущество и провиант для отрядов.
25 мая 1739 года Харитон Лаптев прибыл в Якутск. Дубель-шлюпка «Якутск» была уже готова к походу. Ее экипаж состоял из сорока пяти человек; почти все они были участниками плавания Прончищева.
Окончательно приведя все в порядок, Харитон Лаптев 5 июня повел свое судно вниз по Лене; дощаники с провиантом отправились вместе с ним.
В дельте Лены Лаптеву удалось найти вход в Крестяцкую протоку и к 19 июля он вышел на взморье.
21 июля «Якутск» направился на запад к Хатангской губе, а дощаники, не приспособленные к плаванию в открытом море, Лаптев приказал вести к устью Оленека и сложить провиант в старом зимовье Прончищева.
Возле устья Оленека судно вошло во «льды великие». Дубель-шлюпка шла под парусами и на веслах, команда расталкивала льдины шестами, а иногда пробивала дорогу во льду пешнями. Через неделю, 28 августа, Лаптев достиг восточного входа в пролив, отделяющий остров Бегичева от материка. Пролив был забит неподвижным льдом.
Посланному на берег для описи геодезисту Чекину показалось, что лед прижат к берегу, замыкающему залив с запада; поэтому он принял пролив за открытую с востока бухту, а остров Бегичева — за полуостров. Бухту нанесли на карту под названием Нордвик.
Отойдя от «бухты» Нордвик, «Якутск» направился к северу, чтобы обойти «полуостров» и войти в Хатангский залив. Стремясь избежать сжатия льдами, прижимаемыми ветром к берегу, Лаптев завел дубель-шлюпку в какую-то бухточку, где в течение пяти дней ожидал улучшения ледовой обстановки.
Пробившись через льды, Лаптев 6 августа ввел судно в Хатангский залив. На западном берегу залива виднелось зимовье. Лаптев решил свезти на берег часть провианта на случай, если придется зазимовать в этом месте. Но прежде чем удалось осуществить это намерение, опять задул северный ветер, нагнавший в залив лед.
Снова пришлось искать укрытия, и Лаптев повел дубель-шлюпку на юг вдоль берега. Вскоре показалось еще одно зимовье. Около него «Якутск» вошел в устье маленькой речки и простоял там целую неделю, которая ушла на выгрузку части провианта на берег.
14 августа, когда изменивший направление ветер отогнал лед, Лаптев повел судно вдоль берега к северу. При выходе из Хатангского залива отрядом был открыт остров, названный островом Преображения.
17 августа «Якутск» миновал острова Петра и пошел вдоль берега на запад. Следующий день пришлось простоять из-за льда у островов Фаддея, а затем продвигаться во льду. Только 21 августа «Якутск» подошел к высокому мысу Фаддея. По одну сторону от мыса берег тянулся на юго-запад, а по другую — на запад. Дальнейший путь был прегражден неподвижным льдом. Определить границы льда из-за плотного тумана не представлялось возможным. Поэтому Лаптев послал Чекина на собачьих упряжках выяснить, как далеко в западном направлении простирается лед, а Челюскина — на мыс Фаддея, чтобы поставить там маяк. Вернувшись через двенадцать часов, Чекин доложил, что лед непроходим.
Наступили морозы. Надо было думать о зимовке. Осмотр берега дал неутешительные результаты: здесь не было плавника для постройки жилья. На консилиуме, устроенном Лаптевым 22 августа, было решено возвращаться к Хатангскому заливу. К 27 августа «Якутск» с трудом пробился к зимовью, у которого он находился в начале месяца. Лаптев повел судно дальше на юг. Войдя в Хатангу, он достиг устья ее правого притока — реки Блудной, где проживало несколько семейств безоленных эвенков.
Здесь отряд построил дом и остался на зиму.