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