Постепенно у Миклухо-Маклая сложилось убеждение в необходимости всестороннего исследования Тихого океана. Ему удалось убедить вице-председателя Русского географического общества адмирала Федора Литке добиться для него разрешения отправиться в Океанию на корвете "Витязь". Из средств Географического общества Миклухо-Маклаю выделили 1350 рублей. А нужно было не менее пяти тысяч. Чтобы набрать требуемую сумму, его мать, Екатерина Семеновна, продала ценные бумаги, заложила вещи.
В статье "Почему я выбрал Новую Гвинею?" (она была опубликована посмертно) Миклухо-Маклай писал,
Корвет русского военного флота "Витязь" вышел из Кронштадта в конце октября 1870 года. Миклухо-Маклай должен был ступить на его палубу в одном из больших портов, а пока он отправился в поездку по Европе. Он осматривал музеи, знакомился с учеными. Молодой зоолог испытал гордость, узнав, что его труды известны его новым друзьям и знакомым. Незадолго до этого в "Записках" Российской академии наук был напечатан его отчет об исследованиях губок Тихого океана, а в Лейпциге вышел труд Миклухо-Маклая по сравнительной анатомии - "Мозг позвоночных животных".
В Лондоне он встретился со знаменитым биологом и путешественником Томасом Гексли, изучавшим когда-то Новую Гвинею. Гексли выдвигал предположение об общности происхождения индонезийцев и древних обитателей Европы.
Во время плавания на корвете Миклухо-Маклай пересек Атлантический океан, побывал в Бразилии, в Чили, на некоторых архипелагах Полинезии и Меланезии. Всюду молодой ученый наблюдал, собирал материалы, совершал научные экскурсии.
20 сентября 1871 года Миклухо-Маклай высадился на берегу залива Астролябия, близ селения Бонга, на северо-восточном берегу Новой Гвинеи. Племена и селения были здесь разобщены и постоянно враждовали друг с другом; каждый чужеземец, будь он белый или черный, считался нежелательным гостем.
Миклухо-Маклай первым спустился в шлюпку, за ним последовали его слуги - швед-китобой Ульсен и молодой полинезиец Бой.
Миклухо-Маклай по тропинке среди дикого леса пришел в деревню. Она была пуста. Но возле деревни в густых кустах Миклухо-Маклай заметил первого папуаса Туя, застывшего от ужаса Миклухо-Маклай взял его за руку и привел в деревню. Вскоре вокруг иноземца столпилось восемь папуасских воинов с черепаховыми серьгами в ушах, с каменными топорами в смуглых руках, увешанных плетеными браслетами. Русский гость щедро одарил папуасов разными безделушками. К вечеру он вернулся на корабль, и офицеры "Витязя" с облегчением вздохнули: пока что "дикари" не съели Николая Николаевича.
В следующий раз, когда Миклухо-Маклай вновь съехал на берег, Туй вышел навстречу гостю. Так произошло первое сближение путешественника со страшными "людоедами". На берегу ручья, у моря, матросы и корабельные плотники срубили первый русский дом на Новой Гвинее - дом Маклая.
Ученые-офицеры с "Витязя" провели топографическую съемку местности Бухта с коралловыми берегами - часть обширного залива Астролябия - была названа порт Константин, мысы - именами топографов, делавших съемку, а ближайший остров получил имя Витязь.
"Витязь" продолжил плавание, а Миклухо-Маклай, Ульсен и Бой остались на берегу Новой Гвинеи.