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