В 1876–1877 годах Миклухо-Маклай совершил путешествие в Микронезию и Меланезию. На острове Яп учёный с любопытством рассматривал «каменные деньги» — огромные, грубо обтёсанные камни с отверстиями посередине, имевшие форму мельничных жерновов различной величины, иногда в несколько тонн весом. А на островах Адмиралтейства учёный увидел большую туземную пирогу, мачта и рея которой были украшены человеческими скальпами. У многих поднявшихся на палубу корабля туземцев на спине или груди были привешены какие-то странные предметы вроде метёлок: тонкие ветки, собранные в пучок, были прикреплены к ручке, выточенной из берцовой кости человека. Неужели это и есть пресловутые людоеды? Но мрачные талисманы вскоре получили разъяснение: это был обычай «руен-римата», ношения костей отца или ближайших родственников, если они были знатными или выдающимися людьми.
В июне 1876 года путешественник вновь оказался на Новой Гвинее, на памятном берегу Маклая. Матросы выгрузили припасы, ящики, бочки, подарки для папуасов. Все старые знакомые были ещё живы и очень радушно приняли «караан-тамо». Корабельные плотники построили дом из крепкого строевого леса в окрестностях деревни Бонгу. Новоселье путешественник справлял в кругу папуасов, двух слуг и повара.
Миклухо-Маклай не умел отдыхать. Вновь и вновь неутомимый путешественник поднимался в горы, углублялся в джунгли, пересекал быстрые реки. Из горных деревень он приносил новые черепа, утварь и… новые приступы лихорадки. Ему удалось описать людей и природу берега Маклая на протяжении двухсот миль. Миклухо-Маклай в совершенстве изучил обычаи папуасов, знал их язык, искусство. Он понимал, что вторжение белых неизбежно, поэтому задумал создать из деревень берега Маклая Папуасский союз и самому встать во главе его. Русское правительство отказалось поддержать его в этой затее.
В этот раз учёный прожил на берегу Маклая 14 с половиной месяцев. В ноябре 1877 года в залив Астролябия зашла английская шхуна «Флауэр оф Ярроу». Миклухо-Маклай решил отправиться на ней в Сингапур — привести в порядок коллекции, засесть за книги и статьи о своих открытиях. На прощание он созвал папуасов из окрестных деревень и предупредил их, что приходящие к их берегу белые люди могут оказаться работорговцами и пиратами. Если же здесь появятся белые люди, которые подадут особый «знак Маклая», то папуасы должны доверять им во всём.
Миклухо-Маклай прибыл в Сингапур совершенно больным. В июле 1878 года он переезжает в Сидней. Его сопровождала почти мировая слава и… огромные долги. Письма в Русское географическое общество, содержащие просьбы о помощи, остались без ответа — взамен денег он получил титул барона. Единственную реальную помощь учёному оказал Австралийский музей. При его поддержке Миклухо-Маклай отправляется в новое путешествие — в самое сердце Меланезии, в места, куда ещё не отваживались проникнуть европейские исследователи. На рассвете 29 марта 1879 года он на шхуне «Сэди Ф. Келлер» покинул порт Джексон. Впереди были сто шестьдесят дней плавания по бурному морю, двести тридцать семь дней, проведённых на берегах далёких неисследованных островов, где учёный стал свидетелем случаев каннибализма. Миклухо-Маклай спокойно бродил по селениям людоедов, ел туземный суп из мяса диких голубей, спал прямо под звёздами. Из «страны людоедов» он увёз много новых зарисовок, записок, антропометрических измерений и составленный им словарь местного языка.
В 1882 году, после двенадцати лет странствий, Миклухо-Маклай вернулся в Петербург. На какое-то время он стал героем дня. А потом — новое путешествие. В начале февраля 1883 года Миклухо-Маклай отплывает на Яву. В Батавии он застал русский корвет «Скобелев» и убедил его капитана по пути во Владивосток зайти на Берег Маклая. 16 марта путешественник в третий раз увидел столь знакомую ему бухту… Дети и юноши выросли, его добрые приятели стали стариками, многие умерли… Русские матросы расчистили густой кустарник и посадили новые полезные растения — подарок Миклухо-Маклая папуасам. Он привёз с собой саженцы и семена тыкв, кофейного и цитрусового деревьев, манго, новые виды хлебного дерева. «Караан-тамо» щедро раздавал своим друзьям куски красной китайки, малайские ножи, зеркала, бусы, топоры. С корабля на берег перевезли целое стадо домашних животных — коз, коров и горбатого быка-зебу. При виде быка папуасы от ужаса полезли на деревья…
В июне 1883 года путешественник прибыл в Сидней. Почти три года он провёл в Австралии. Здесь он женился, здесь он начал ожесточённую борьбу против всевозможных «расовых теорий», концепций «низших» и «высших» рас, утверждающих человеческое неравенство. Он писал Бисмарку, чтобы «все белые взяли на себя защиту прав темнокожих туземцев островов Тихого океана от бессовестной, несправедливой и зверской эксплуатации» и посылал телеграммы русскому царю Александру III, умоляя его заступиться за папуасов.