Узнав, что Толстой заинтересовался «некоторыми эпизодами» его странствий, Миклухо-Маклай 19 сентября 1886 г. послал великому русскому писателю из Петербурга свое первое письмо, сообщив, что после возвращения в Россию, на пути из Киева в Москву, хотел навестить его. Необходимость быть как можно раньше в Петербурге заставила Николая Николаевича отложить поездку в Ясную Поляну. 19 сентября 1886 г. Миклухо-Маклай послал Толстому две статьи о пребывании в Новой Гвинее, в ответ на которые писатель послал ему свое знаменитое письмо. Толстой благодарил Миклухо-Маклая за интересные брошюры, которые вызвали у него восхищение его путешествиями. «Вы первый,—писал Толстой,— несомненно, опытом доказали, что человек везде человек, то есть доброе, общительное существо, в общение с которым можно и должно входить только добром и истиной, а не пушками и водкой. И вы доказали это подвигом истинного мужества, которое так редко встречается в нашем обществе, что люди нашего общества даже его и не понимают».

1887 год был особенно тяжелым для Миклухо-Маклая. В начале февраля он выступил на общем собрании Географического-общества и сообщил, что он должен по домашним обстоятельствам выехать в Сидней. Касаясь подготовки к печати первого тома описания своих путешествий, который был «почти что готов», он сказал: «Несмотря на то что я старался не терять-времени, работа моя подвигается далеко не так быстро, как я ожидал, чем отчасти я обязан сильному нездоровью, которое не раз заставляло меня работать не так, как я желал». Николай Николаевич рассчитывал вернуться из Австралии в Петербург «приблизительно в мае месяце, чтобы посвятить лето и осень на продолжение и окончание» своих работ. Подробнее о причинах своего отъезда в Австралию Миклухо-Маклай написал старшему брату Сергею. «Я решил,— писал он,— перевезти жену и моих ребят на год или полтора в Европу, почему и еду в Сидней, где без меня мои очень важные зоологические, анатомические коллекции все пропадут».

В этом же письме Миклухо-Маклай подвел печальный итог своей многолетней борьбы за осуществление проекта Берега Маклая. «В деле относительно Берега Маклая,— писал Николай Николаевич, — я потерпел почти полное фиаско. Подобным же фиаско заключился поднятый мною вопрос об основании русской колонии на островах Тихого океана». Накануне отъезда в Австралию Миклухо-Маклай передал в Этнографический музей Академии наук свои рукописи и рисунки. В архиве Академии наук сохранилась расписка сотрудника этого музея о том, что он 11 марта 1887 г. получил от Миклухо-Маклая для этого музея «3 жестянки с рукописями и рисунками, 1 небольшой кожаный чемодан с тем же, 1 большой портфель с бумагами и рисунками, 1 жестяную трубку с картами». 16 марта, перед самым отъездом в Австралию, путешественник передал в музей свой портрет и карту Малайского архипелага. Книги свои он отдал Петербургскому университету.