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