Российское научное общество благосклонно встретило молодого учёного. Миклухо-Маклай выступил с докладами в Москве и Петербурге. Первый доклад – о развитии мозга позвоночных – был интересен только узким специалистам. Второй же – о первой попытке создания биологической станции на Сицилии – вызвал живой интерес у последователей разных научных направлений. Николай Николаевич призвал научное сообщество строить такие исследовательские станции, чтобы «каждый зоолог без различия национальности мог пользоваться для своих научных занятий всеми оставленными приборами». И его призывы были услышаны. Первая российская зоологическая станция была создана в Севастополе уже в 1871 году.
Научная карьера Миклухо-Маклая пошла в гору. Он познакомился с русским академиком Карлом Бэром, который фактически стал научным руководителем Николая Николаевича. Престарелый Бэр в последние годы жизни занялся изучением первобытных племён. Маклай ознакомился с работами учёного о народах Тихого океана и серьёзно увлёкся ими. Бэр был категорически против подхода некоторых западных антропологов, которые делили расы на полноценные и неполноценные. Однажды Николаю Николаевичу попалась книга немецкого этнолога Отто Финша «Новая Гвинея». Он писал, что якобы кожа у жителей Новой Гвинеи – папуасов – не такая, как у современных людей, а жёсткая, «первобытная», и волосы растут пучками. Миклухо-Маклай, который так же, как и Карл Бэр, стал ярым сторонником равноправия человеческих рас, начал серьёзно задумываться об экспедиции на Новую Гвинею для проведения антропологических исследований.
Почему Миклухо-Маклай выбрал именно этот остров с тяжёлым жарким климатом, населённый дикими племенами? Об этом он написал позже в статье «Почему я выбрал Новую Гвинею». Этот второй по величине остров в мире, после Гренландии, был давно открыт, но практически не изучен. Даже точные его размеры были неизвестны. Некоторые учёные того времени считали, что Новая Гвинея является частью некогда затонувшей прародины человечества – загадочного материка Лемурии. Миклухо-Маклай в Лемурию не верил, но справедливо считал, что изучение местного населения, живущего изолированно от остальной цивилизации на протяжении тысяч лет, поможет приоткрыть тайну происхождения и расселения по планете человечества.
Осенью 1869 года Миклухо-Маклай представил Совету Географического общества проект экспедиции в Новую Гвинею. Глава общества адмирал Литке сначала очень скептически отнёсся к инициативе Миклухо-Маклая. Всё-таки авторитет молодого учёного в науке был пока что не настолько весом, чтобы выделять серьёзные государственные деньги на его идеи. Однако при личной встрече Николаю Николаевичу удалось переубедить седого адмирала, вспомнив о прошлых кругосветных путешествиях самого Литке. Адмирал обещал оказать Миклухо-Маклаю полную поддержку и вскоре выделил для него финансирование из средств Географического общества, а также место на одном из русских кораблей, отправлявшихся в кругосветное плавание.
В полдень 8 ноября 1870 года корвет «Витязь», на котором двадцатичетырёхлетний Миклухо-Маклай отправился к берегам Новой Гвинеи, вышел из Кронштадта.
По пути корвет посетил остров Пасхи, где Николай Николаевич заинтересовался гигантскими каменными статуями. На острове Самоа, в Полинезии, Миклухо-Маклай нанял двух помощников: бывшего китобоя, шведского матроса Ульсона и полинезийского юношу Боя. 19 сентября 1871 года «Витязь» бросил якорь на северо-восточном берегу Новой Гвинеи, в заливе Астролябия. Этот залив был открыт и нанесён на карту ещё в 1827 году французским мореплавателем Дюмон-Дюрвилем. Однако ни сам француз, ни другие исследователи не высаживались здесь на берег.
Отказавшись от охраны, Миклухо-Маклай вместе с Ульсоном и Боем сели в маленькую лодку и вскоре причалили к песчаному пляжу. Маклай не собирался терять время и решил немедленно познакомиться с местными жителями. Однако Ульсон и Бой в джунгли идти наотрез отказались. Тогда Маклай в одиночестве углубился в лес по едва заметной тропинке, которая привела его в пустую туземную деревню. Только тлеющий костёр и брошенные второпях вещи указывали, что жители покинули деревню недавно и, возможно, скрывались в джунглях. Вдруг рядом раздался шорох. Присмотревшись, Маклай заметил в ближайших зарослях испуганного папуаса. «Я медленно приблизился к дикарю, – вспоминал путешественник, – и молча подал ему красную тряпку, которую он принял с видимым удовольствием и повязал её себе на голову». Путешественник ткнул себя пальцем в грудь и сказал:
– Маклай.
Папуас в свою очередь тоже ткнул себя пальцем в грудь и сказал:
– Туй.
Так Николай Николаевич познакомился со своим будущим другом и проводником в мир аборигенов – Туем.