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