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