19 сентября 1871 года «Витязь» встал на якорь в заливе Астролябии. До берега было всего в 100–150 м. Как описывал позднее свое путешествие Миклухо-Маклай, громадные деревья, росшие у воды, спускали свою листву до самой воды. Открытым в бухточке был лишь небольшой песчаный мыс. Вскоре на нем появились дикари. После долгих совещаний один из них отделился от группы и, неся кокосовый орех, положил его у воды. Мимикой туземец показал, что кокос предназначен для пришельцев, затем быстро скрылся в чаще леса. «Я обратился к командиру с просьбой… дать мне шлюпку без матросов, приказал обоим слугам спуститься в шлюпку и отправился знакомиться с моими будущими соседями». Знакомство состоялось.

Прошло несколько дней и на берегу застучали топоры, матросы расчистили площадку, построили недалеко от берега хижину на сваях и водрузили мачту. На ней был поднят российский флаг. Что обеспечивало безопасность путешественника? Прежде всего, его твердое намерение жить в дружбе с туземцами. Конечно, были у него винтовки, револьверы и шесть мин, закопанных вокруг хижины. Но, главное, была убежденность, что папуасы такие же люди и с ними можно жить в мире и добрососедстве. Так началось первое более чем годичное пребывание Н.Н. Миклухо-Маклая на берегу Новой Гвинеи. Было все: опасности, нужда, болезни, смерть одного из двух слуг. Однако главным был мир и дружественные отношения с туземцами. Среди папуасов «Руссо Маклай» стал самым уважаемым человеком. Тем не менее, как вспоминал Н.Н. Миклухо-Маклай, будучи не уверен в успешном завершении экспедиции, «я указал… командиру и офицерам место, где зарою в случае надобности (серьезной болезни, опасности от туземцев и т. п.) мои дневники и заметки. Место это находилось под большим деревом, неподалеку от хижины».

Приблизительно через год после того как Н.Н. Миклухо-Маклай высадился на берег Новой Гвинеи в Европе распространились слухи о его смерти. Одна из австралийских газет написала, что зашедшее в залив Астролябия купеческое судно нашло в живых только одного из слуг Н.Н. Миклухо-Маклая. В России заметку под заглавием «Миклухо-Маклай и его кончина» напечатал «Кронштадтский вестник». По приказанию великого князя Константина Николаевича к Новой Гвинее срочно был направлен клипер «Изумруд». На него специально перевели даже одного из офицеров с «Витязя», знавшего место, где Н.Н. Миклухо-Маклай намеревался закопать свои научные заметки. Подходя к заливу Астролябия 19 декабря 1872 года, команда клипера только и задавала вопрос: «Жив ли Маклай?» Вскоре один из офицеров заметил на берегу русский флаг. Показались идущие к клиперу папуасские пироги. В одной из них был европеец. Пироги приблизились, и стало ясно, что это Н.Н. Миклухо-Маклай. Команда прокричала «ура!». «По входе Маклая на клипер не было конца рукопожатиям, поздравлениям и разным вопросам». К дереву неподалеку от места, где стояла хижина Н.Н. Миклухо-Маклая командир «Изумруда» приказал прибить медную доску с надписью:

«VITIAS. Sept. 1871.

MIKLOUHO-MAKLAIY.

ISOUMROUD. Dec. 1872.»

С возвращением в Европу к Н.Н. Миклухо-Маклаю пришла мировая известность. «Меня здесь везде в высшей степени любезно и предупредительно встречают, — писал он, — так как много здесь болтали в прошлом году о моем путешествии и предполагаемой смерти».

Впрочем, едва оставив берег Новой Гвинеи, находясь еще на «Изумруде» Н.Н. Миклухо-Маклай начал думать о втором путешествия в Новую Гвинею. Состоялось оно через четыре года. На этот раз на берегу Маклая — так теперь стал называться северо-восточный берег Новой Гвинеи, Н.Н. Миклухо-Маклай пробыл почти полтора года, с 27 июня 1876 года по 10 ноября 1877 года. На карте Новой Гвинеи появились русские названия: гавань Великого Князя Константина, гавань Великого князя Алексея, гора князя Мещерского, пролив Изумруда и др.

К этому времени относится и возникновение у Н.Н. Миклухо-Маклая идеи присоединения берега Новой Гвинеи, носящего его имя, к России. Конечно, идея родилась не на захватнической почве, а на сугубо гуманной. Колониальные устремления европейских государств в Океанию и Малайзию пугали Н.Н. Миклухо-Маклая. Величайший гуманист, он был искренне убежден, что под скипетром Российской империи его новым друзьям, папуасам, будет, несомненно, лучше. О написанном в это время открытом письме английскому губернатору островов Фиджи А. Гордону по поводу отношения колонизаторов к местным жителям он вспоминал: «Когда я писал сэру Артуру, мне не раз приходила на ум мысль, что мои увещевания пощадить “во имя справедливости и человеколюбия” папуасов походят на просьбу, обращенную к акулам, не быть такими прожорливыми».

В январе 1878 года после второго пребывания на Новой Гвинее Н.Н. Миклухо-Маклай прибыл в Сингапур. Здесь его свалила болезнь. Болел он почти полгода. Здесь же Н.Н. Миклухо-Маклай получил письмо от вице-президента Русского географического общества П.П. Семенова-Тяньшанского. Письмо расстроило его. П.П. Семенов-Тяньшанский не только отказывался содействовать его планам присоединения «берега Маклая» к России, но и упрекал за переход «с почвы чисто научной на почву чисто практическую». Да и в «высших инстанциях» к планам Н.Н. Миклухо-Маклая отнеслись явно с прохладцей. В своем ответе П.П. Семенову-Тяньшанскому он писал: «Причина отрицательного решения высших инстанций была “отдаленность страны и отсутствие в ней связи с русскими интересами”. Замечу на это, что “отдаленных” стран уже теперь почти не существует, а тем более в будущем; что кроме русских интересов есть еще общечеловеческие…, которые по своей значительности… должны становиться делом просвещенных и гуманных правительств».

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

Почти сразу с приездом в Петербург Н.Н. Миклухо-Маклай с присущей ему энергией приступил к реализации своего плана «закрепления за Россией» части Новой Гвинеи или хотя бы одной из групп небольших островов в Тихом океане. Он встретился и обсудил свое предложение с великим князем Алексеем Александровичем, ставшим к тому времени генерал-адмиралом, с управляющим Морским министерством вице-адмиралом И.А. Шестаковым, неоднократно наезжал в Гатчину, где был принят Александром III. Как записал в своем дневнике И.А. Шестаков, Н.Н. Миклухо-Маклай «склонил государя занять или приобрести в Полинезии какое-нибудь складочное (складское. — Ю. К.) место для наших судов». Путешественник предлагал занять острова Адмиралтейства или острова Пэлау. Идею Н.Н. Миклухо-Маклая император и генерал-адмирал одобрили. Она показалась им не только вполне реальной, но и перспективной. Вскоре управляющий Морским министерством получил приказание разработать план «секретной экспедиции с участием путешественника», предложившего себя в качестве «проводника и переводчика». Цель экспедиции — «изыскание морской станции в Тихом океане».