В декабре 1873 года Миклухо-Маклай отправился на берег Папуа-Ковиай на западе Новой Гвинеи. По слухам, именно здесь обитали самые страшные людоеды. Это, естественно, не остановило отважного путешественника. В то время как Маклай занимался научными исследованиями в горах, его хижина была разграблена, а охранявшие её папуасы убиты. Но преступление совершили не какие-то «людоеды», а давно известная шайка разбойников, которую возглавлял вождь нескольких горных сёл по имени Саси. Он был охотником за рабами и теперь собирался совершить новый набег, чтобы убить Маклая. Узнав об этом, Николай Николаевич взял с собой двух помощников и отправился прямиком в деревню Саси. Увидев спокойно приближающего белого человека, главарь растерялся и спрятался в своей пирóге (лодке). Маклай вытянул его за шиворот, после чего связал и передал голландским властям, которые в то время контролировали эту часть Новой Гвинеи.
На Малаккском полуострове, южной оконечности острова Индокитай, Миклухо-Маклай долго искал загадочных оран-сакаев – «людей леса». По слухам было известно, что они небольшого роста, черны, живут в непроходимых джунглях и поражают врагов отравленными стрелами. Маклаю пришлось дважды пересечь джунгли полуострова, кишащие крокодилами, тиграми и огромными змеями. Несмотря на все опасности, учёный нашёл загадочное племя и изучил его. Оран-сакаи не были похожи на жителей Малаккского полуострова – малайцев, ростом они напоминали скорее жителей Филиппин – негритосов, а обликом – папуасов Новой Гвинеи. Маклай сделал вывод, что «жители леса» – последние потомки древнейшего населения Индокитая, которое многие тысячи лет назад перебралось на острова Океании.
В начале 1876 года Миклухо-Маклай посетил Каролинские острова, находящиеся к северу от Новой Гвинеи. Здесь учёный впервые описал удивительные каменные деньги, которые сохранились и до наших дней. Они похожи на мельничные жёрнова диаметром от 30 см до 2 метров. Местные жители высекали эти деньги из известняка, который привозили на лодках с соседнего острова, затем полировали, а в центре пробивали отверстие. Самые большие экземпляры весят несколько тонн и равны примерно 1000 долларов США. Такой камень невозможно перенести с места на место, поэтому, если им расплатились, считается, что он просто поменял хозяина.
Летом 1876 года уже знаменитый на весь мир путешественник вернулся на Берег Маклая. В этот раз его целью были не только научные исследования. «Я держу слово и возвращаюсь в Новую Гвинею не только как естествоиспытатель, а как «покровитель» моих чёрных друзей «Берега Маклая». Я решился защищать… их независимость в случае европейского вторжения», – написал Николай Николаевич в письме Географическому обществу. Когда Миклухо-Маклай сошёл на берег, к лодке сбежались туземцы из соседних деревень. Даже женщины и дети, которые раньше прятались при его появлении, пришли поприветствовать Маклая. Все наперебой приглашали дорогого гостя поселиться в своей деревне. Но он снова построил дом в отдалении, выбрав живописное место в окрестностях деревни Бонго.
Николай Николаевич стал практически старейшиной племён Берега Маклая. Его снова звали на свадьбы и похороны, он помогал советом, лечил больных. Его авторитет был так велик, что однажды он предотвратил войну между горными папуасами и жителями побережья. Как-то раз Туй пришёл к Маклаю и заявил, что жители деревень Бонгу и Горенду заключили военный союз против горных папуасов. Якобы те с помощью колдовства убили двух молодых воинов из Горенду. Туй попросил Маклая наслать на горцев землетрясение, чтобы победа была гарантирована. В ответ Маклай твёрдо ответил, что ни землетрясения, ни войны он не допустит, пока живёт здесь. И туземцы послушались Маклая, отменив военный поход.
Маклай прожил среди папуасов чуть больше года. За это время он подробнее изучил природу и жителей Новой Гвинеи, отдаляясь в походах от своей хижины на 200 км. Маклай в совершенстве изучил обычаи папуасов, их язык и промыслы.
В конце 1877 года в залив Астролябия случайно заплыло английское судно. Миклухо-Маклай решил добраться на нём до Сингапура, чтобы поправить здоровье, а также плотно заняться научными статьями. Перед отплытием Николай Николаевич собрал представителей всех окрестных деревень и предупредил, что далеко не все белые хорошо обращаются с чернокожими людьми. Рано или поздно на Берег Маклая могут приплыть злые белые люди. В этом случае он советовал уводить женщин и детей в горы и с осторожностью относиться к пришельцам. Николай Николаевич знал, о чём говорил: в своих путешествиях он повидал много несправедливости со стороны «цивилизованных» европейцев по отношению к темнокожим аборигенам Океании.