Обрадованный этими известиями, Мельвиль решил отправиться немедленно на поиски де-Лонга и его товарищей и найти их во что бы то ни стало живыми или мертвыми. Он выехал на другой день на север на нартах, запряженных свежими и сильными собаками, и через два дня достиг берега океана. Там он нашел описанный в записке де-Лонга высокий шест и под ним сложенные в кучу, занесенные снегом, все вещи, к величайшему удивлению и восторгу якутов, особенно восхищавшихся двумя винтовками…
Затем Мельвиль направился в Булунь, чтобы там запастись провизией и организовать дальнейшие поиски де-Лонга. Свирепствовала пурга, угрожавшая мучительной смертью людям и собакам; душная, леденящая и колючая, она окутывала их. Собаки (их было 29) поминутно останавливались; они не в силах были двигаться против ураганного снежного ветра, и никакие, побои не помогали. Вперед подвигались медленно, ночуя в заброшенных юртах, заполненных снегом, но шли все время по следам де-Лонга и его товарищей, по всем зигзагам их пути, согласно описанию Ниндемана и Нороза. Следы сохранились: на льду разных рукавов дельты Лены, так как ветер смел со льда весь снег; но через несколько дней такого мучительного пути следы эти исчезли, из чего Мельвилю стало ясно, что он где-то взял неправильное направление. Но он был не из тех людей, которые легко, теряют мужество. Нет! Полузамерзший, истощенный от голода, питаясь на ночлегах исключительно брошенными остатками гнилой рыбы и оленьих костей, из которых они варили себе жалкий вонючий «суп», Мельвиль среди непрекращавшейся пурги, леденившей кровь, еще 5 дней боролся со стихией, боролся с холодом и голодом, стараясь вновь напасть на следы несчастных де-Лонга и и его товарищей…
В особенности Мельвилю хотелось найти то место у берега одного из рукавов Лены, где они похоронили умершего от истощения матроса, датчанина Эриксена, по обычаю моряков (т.-е. бросив завернутое в саван тело его в реку). По описанию Ниндемана, это было возле одной покинутой юрты, над дверьми которой де-Лонг, чтобы легче было потом найти это место, прикрепил доску с надписью о событии, а внутри юрты оставил винтовку, так как даже и такая тяжесть уже была не под силу ослабевшим путникам, силы которых быстро таяли.
Но все усилия Мельвиля были тщетны; в довершение всех бед, благодаря ужасной пище, состоявшей из вонючих отбросов, которыми в обыкновенное время побрезговали бы даже и собаки, Мельвиль схватил сильнейшую дизентерию. Поэтому он решил бросить дальнейшие поиски и вернуться в Булунь, а оттуда отправиться вместе с помощником исправника Ипатьевым в Верхоянск, а затем дальше в Якутск, чтобы там организовать весною экспедицию для розыска де-Лонга и его товарищей. Решение это было совершенно правильным, так как если де-Лонгу и его спутникам до сих пор не посчастливилось встретиться с кем-либо из туземцев, то они, конечно, уже погибли, и нечего торопиться с розыском их трупов ценою своей собственной жизни. Если же им это удалось, то они уже спасены и сами доберутся до Верхоянска.
После мучительного десятидневного пути в сильнейшую пургу и жестокий мороз Мельвиль, наконец, 27 ноября вернулся в Булунь, почти мертвый от истощения и перенесенных мучений. А через два дня прибыл Ипатьев с большим запасом хлеба, мяса и прочей провизии; но Мельвиль и тут не хотел терять даром времени. Он отдыхал всего три дня и, далеко еще не оправившись, поспешил в Верхоянск, отстоящий на 900 верст. Беспощадный к самому себе, повинуясь только чувству самоотверженного долга, он поспешил воспользоваться содействием Ипатьева, помчался с ним на свежих переменных оленях в Верхоянск в 50-градусный мороз. Ехали день и ночь, нигде не ночуя, делая лишь короткие остановки для чаепития или обеда, и через 5 суток, вечером 6 декабря, прибыли, наконец, в Верхоянск, отмахав 900 верст.
В Верхоянске Мельвиль пробыл немного менее двух недель, и затем, еще не отдохнув как следует от всех ужасов и страданий, перенесенных после крушения «Жаннеты», поспешил в Якутск с целью организовать экспедицию для продолжения поисков без вести пропавших де-Лонга и его товарищей или, вернее, их тел, так как в окончательной их гибели он уже не сомневался.
Из Якутска Мельвиль вернулся со свежими силами в конце февраля следующего 1882 года в сопровождении Ниндемана и еще нескольких товарищей и продолжал свои поиски, исследуя обширный район дельты Лены к северу от Булуни от того места, откуда де-Лонг послал Ниндемана и Нороза за помощью. Стояли лютые морозы и свирепствовали снежные метели (пурга); все изнемогали от холода и усталости. И лишь спустя почти месяц, на высоком берегу одного из рукавов дельты Лены, в 150 верстах к северу от Булуни, Мельвиль увидел торчащий из сугроба высокий шест. Разрыв снег, увидели висящую на этом шесте американскую винтовку; затем, продолжая раскопку, нашли трупы де-Лонга, д-ра Эмблера и повара-китайца Э-Сема, а потом на небольшом расстоянии друг; от друга трупы и остальных девяти товарищей. Возле трупа де-Лонга лежала его маленькая записная книжка, прозванная Мельвилем «ледяным дневником».