ניקולאי הפליג על ספינה מצרית לג'דה, שם שהה 18 יום. הוא התיישב בביתו של איש עסקים צרפתי, שהתרשם מהתלהבותו המדעית של הצעיר. מיקלוחו שט מדי יום לשוניות אלמוגים. תנאי המחקר היו קשים: החום לא ירד מתחת ל-35 מעלות צלזיוס אפילו בלילה, לרוב לא היה איפה לגור, התקפי המלריה לא פסקו והוא פיתח דלקת לחמית בגלל האבק המדברי. בקושי רב חזר ניקולאי לסואץ. הוא ליקט אוסף ספוגים, המאוחסן כעת במוזיאון לזואולוגיה של המכון הזואולוגי של האקדמיה הרוסית למדעים. לטענת הביורגף ד. טומרקין, מסעו של מיקלוחו לים האדום מילא תפקיד חשוב בגורלו של המדען. שם הופיעו התכונות האופייניות לפעילותו: נטייה לעבוד לבד והעדפה לשיטות מחקר נייחות. הוא הפך לחוקר טבע רחב יריעה, שהגיע לבסוף לשאלות על הפעילות האנושית ותרבותו ביחס לסביבתו הגאוגרפית.
המשלחת הראשונה לגינאה החדשה.
הכנת המשלחת.
עד חזרתו של ניקולאילרוסיה מצבה הכלכלי של משפחתו השתפר מעט. לאחר שקיבל כסף מאמו, נסע ניקולאי מאודסה לסראטוב, שבסמוך אליה הייתה אחוזה של קרובי משפחתו. בסמוך לסמרה הוא לקה בהתקפי מלריה קשים. גם מצבו הנפשי היה קשה. הוא התלונן במכתבים לדורן על כך שאינו רגיל עוד לרוסיה והתעצבן מהמציאות והאנשים סביבו. הוא נסע למוסקבה, שם חזרו התקפי המלריה כשהם מלווים בהזיות והתעלפויות. באוגוסט הוא בכל זאת הגיע לסראטוב, שם התאושש מעט בזכות טיפול של קרובי משפחתו. במוסקבה או בסראטוב הוא קיבל מרשם רפואי לצריכת כינין, אשר מקל על התקפי המחלה.
לאחר חודש בסרטוב, ניקולאי עזב למוסקבה לקונגרס השני של הנטורליסטים הרוסים, שהתקיים בין התאריכים 1–11 בספטמבר 1869. הוא נרשם למסלול לזואולוגיה ולאנטומיה השוואתית, בו הוצגו 69 דיווחים, שניים מהם שלו: על התפתחות המוח בכימרה ועל הקמת תחנה זואולוגית על בסיס חומרים שנאספו יחד עם דורן במסינה. לאחר הקונגרס נסע ניקולאי לסנקט פטרבורג, שם הוא נשכר על ידי האקדמאי ברנדט כדי לעבד ולפרסם את אוספי הספוגים שנאספו על ידי קארל בר ואלכסנדר מידנדורף . המדען השלים משימה זו במהירות ופרסם שני דיווחים בגרמנית במהדורות האקדמיה למדעים של בסנט פטרבורג. זה תרם לקבלתו לשורות החברה הגאוגרפית הרוסית.
כבר ב־5 באוקטובר הופיע ניקולאי בישיבה משותפת של האגפים לפיזיקה ולמתמטיקה של החברה הגאוגרפית עם דו"ח על המסע לים סוף. באותם ימים נפגש עם הנסיך קרופוטקין, אשר ב"הערותיו של מהפכן" תיאר אותו כ"בן אדם עצבני שסובל כל הזמן מקדחת". קרופוטקין היה באותה תקופה מיוזמי משלחת קוטב גדולה, אך סיכויי מימונה היו קלושים. ככל הנראה, הדבר הוביל את ניקולאי ב־8 באוקטובר להגיש לחברה הגאוגרפית הרוסית את פרויקט משלחתו לאוקיינוס השקט. הפרויקט הוגש לנשיא החברה פיוטר סמיונוב, אך נתקל בהתנגדותו של סגן הנשיא הרוזן ליטקה. ב-28 באוקטובר 1869 מועצת החברה החליטה לאמץ את התוכנית של מיקלוחו. הוחלט לפנות למשרד הצי כדי להביא את ניקולאי לאוקיינוס השקט ובחזרה באונייה צבאית.
משם ניקולאי נסע לינה לצורך הכנת מונוגרפיה על התפתחות המוח בדגים. בעיר הוא התיישב אצל פרופסור הילדברנד, שבתו אורליה קיימה עמו יחסים רומנטיים. במקביל להכנת המונוגרפיה "חומרים לנוירולוגיה השוואתית של בעלי חוליות" הוא קרא ספרות על אוסטרליה ואוקיאניה. בפברואר 1870 כתב ניקולאי לאוסטן-סקן מהחברה הגאוגרפית כי בכוונתו להישאר באיים של דרום האוקיינוס השקט לפחות 3–4 שנים. מועצת החברה אישרה את התוכניות של ניקולאי ב-11 במאי 1870 והקצתה לו גימלה בגובה 1,200 רובל. ב־21 במאי הודיע שר הצי כי התקבל אישור מלכותי לקחת את מיקלוחו על קורבטת ״ויטיאז״, אך מבלי לספק גמלה מהצי. יציאת המשלחת נקבעה לספטמבר.
מהעיר ינה נסע ניקולאי לגותה, שם שוחח עם פטרמן, אך מבלי לחשוף את תוכניותיו. ב-11 במרץ ניקולאי גילה כי הסופר איוון טורגנייב והזמרת פולין ויארדו נמצאים בוויימאר. הוא כתב לאחותו אולגה: "די מהר התחברנו. חבל שאני טובע בעבודה, אחרת הייתי נוסע לעיתים קרובות יותר לווימאר". הקשר של ניקולאי עם הסופר נמשך עד מותו של טורגנייב בשנת 1883.
מבחינה חומרית, ניקולאי היה עדיין תלוי לחלוטין באמו, איתה העדיף לתקשר באותה תקופה דרך אחותו אולגה. באפריל 1870 החליט המדען לנסוע ללונדון להתייעץ עם מומחים ולרכוש ציוד מדעי. לאחר ששקע בחובות ביינה, נסע לליידן בשארית כספו, שם קיבל צ'ק מאמו בצירוף מכתב לפיו הוא לא יכול לבנות עוד על דבר. בלונדון הוא שהה שבוע, ופגש את תומאס הנרי האקסלי. האקסלי הכיר את ניקולאי דרך מכתביהם של הקל ודורן וקיבל את ניקולאי בלבביות. האקסלי שיתף את זיכרונותיו מטיולו באוסטרליה ובגינאה החדשה בשנים 1846–1850, והגיש גם המלצה לקבלת פנים באדמירליות. ניקולאי הוצג בפני נשיא האגודה הגאוגרפית המלכותית, סר רודריק מורצ'יסון, שהבטיח לשגר לו מכתב המלצה לכל הקונסולים האנגלים באיי האוקיינוס השקט, אך הדבר התברר כבלתי אפשרי. רכישת הציוד כשלה בשל המחירים הגבוהים בבריטניה. ב-30 באפריל עזב ניקולאי בדחיפות את לונדון עקב החמרה במלריה וחזר ליינה דרך בריסל. הוא לא יכול היה לנסוע לרוסיה בגלל חוסר כסף, ורק ב-24 במאי העבירה לו אמו סכום נוסף. לאחר שהכיר בברלין את רודולף וירכו והשאיר בלייפציג ספר לפרסום, הפליג מקלאי ב־17 ביולי 1870 משצ'צ'ין לסנקט פטרבורג.
לפני ההפלגה.
המכשול העיקרי של ניקולאי לפני היציאה לימים הדרומיים היה שמשרד הצי לא התכוון לשנות עבורו את מסלול הספינה ״ויטיאז״. לכן הוא נאלץ להגיע לגינאה החדשה לבדו מבטאוויה (כיום ג'קרטה) שבאיי הודו המזרחיים ההולנדיים. הגמלה של החברה הגאוגרפית הרוסית לא הספיקה. המדען עצמו העריך את תקציב המשלחת בלפחות 5,000 רובל. במצב זה, הוא פנה שוב אל אמו בבקשה למכור את חלקה במניות חברת ״סמוליוט״ על חשבון הירושה. אמו סירבה בעדינות, מכיוון שבעצת אחיה היא חסכה כספים לרכישת נכס. המדען ניסה ללוות כסף ממכרים, והעביר לבסוף את אוסף הספוגים שלו למוזיאון הזואולוגי תמורת החזר על עלויות "האיסוף, האחסון וההובלה של האוספים הללו", אשר העריך ב-300 רובל. חלק מחברי החברה הגאוגרפית הרוסית סיפקו לו ציוד חינם: מיכאיל ריקצ'יוב נתן לו חדש ברומטר חדש וסגן אדמירל סמיון זליונוי הביא לו מדחום למים עמוקים. אך כל זה לא הספיק. האקדמאי סמיונוב הצליח לעניין את הנדבנית המפורסמת, הדוכסית ילנה פבלובנה. ניקולאי קיבל את הזמנתה לאורניינבאום , שם שהה בפאר ויצר קשרים מועילים. כתוצאה מכך הצליח להשיג שינוי בנתיב הספינה.
ב־19 באוקטובר 1870 הודיע ניקולאי באספה הכללית של החברה הגיאוגרפית הרוסית כי הוא מתכנן משלחת בת 7 או 8 שנים. התוכנית הייתה שאפתנית, אך מעורפלת. חלק מהנוכחים הביעו תמיהה, מכיוון שמחקרים על איים טרופיים נראו מיותרים עבור רוסיה. עם זאת, על פי אמנת החברה הגיאוגרפית הרוסית, לא היה צורך באישור התוכניות על ידי האספה הכללית. עד מהרה קיבל המדען מכתב המלצה פתוח לכל הקונסולים הרוסים בנמלים ובאיים של האוקיינוס השקט, ומשרד הפנים של האימפריה הרוסית שלח דרכון זר לחברה הגאוגרפית הרוסית על שם "האציל מיקלוחו-מקלאי, שנשלח למטרות מדעיות". כך הפך שמו הכפול לרשמי.
ב־29 באוקטובר ביקר באוניה ״ויטיאז״ הדוכס הגדול קונסטנטין ניקולאביץ' , שניהל שיחה ארוכה עם ניקולאי. הוחלט ששנה לאחר הורדתו תבקר ספינת מלחמה רוסית בגינאה החדשה; במקרה שהחוקר לא יהיה בחיים, הספינה תאסוף כתבי יד ארוזים בגלילים הרמטיים. ביום ההפלגה, ה-8 בנובמבר 1870, ניקולאי בן ה-24 שלח מכתב לדוכס ולאמו. במכתב נאמר: .
ההפלגה לגינאה החדשה.
לאחר שעזבה את קרונשטט, ב-14 בנובמבר הגיעה ה״ויטיאז״ לקופנהגן. ניקולאי ירד שם ומ-17 בנובמבר ועד 4 בדצמבר ביצע מסע באירופה בערים המבורג, ברלין, ינה, גותה, האג ואוסטנדה ויצר קשרים במשרד המושבות ההולנדי. במסעו הוא רכש את הציוד הדרוש לו ואת החשבונות שלח לנסיך משצ'רסקי. לאחר מכן לקח מעבורת לפלימות' שבאנגליה וחבר בחזרה לאונייה. במהלך שהות קצרה בלונדון פגש ניקולאי את אלפרד ראסל וולאס, מהוגי תאוריית הברירה הטבעית. בשיחה עמו הצהיר ניקולאי שהוא יוכל ללמוד משהו על הילידים רק אם יחיה ביניהם. לאחר היציאה מאנגליה, בלילה סוער ב-29 בדצמבר 1870, שיקעה ה״וויטיאז״ ספינת מפרשים גרמנית שנלכדה על ידי הצרפתים והפליגה ללא אורות. היה צורך צריך להפליג לפונשל שבפורטוגל לתיקונים ולחילוץ הניצולים. הקורבטה נכנסה לשם ב-31 בדצמבר והמשיכה לאיי כף ורדה, שם עמדה במשך שלושה שבועות, שם חקר ניקולאי חקר ספוגים על החוף.
ב־3 בפברואר ערך ניקולאי ניסוי מדידות טמפרטורת מי האוקיינוס בעומק רב. הניסוי נמשך שלוש שעות, ועל הקרקעית בעומק 1829 מ׳ נמדדה טמפרטורה של +3.5 מעלות צלזיוס, בעוד שעל פני המים היא הייתה +27.56 מעלות צלזיוס. כבר בשנת 1871 כתב המדען מאמר בנושא זה לחדשות החברה הגאוגרפית הרוסית. ב־7 בפברואר חצתה הקורבטה את קו המשווה (באותו יום ניקולאי ניתח את מוחו של כריש כחול שנתפס על ידי מלחים), ובבוקר 20 בפברואר הגיעה לריו דה ז'ניירו. ניקולאי הגיע מיד לבית החולים העירוני, שם קיבל הזדמנות לבחון כמה מאות אנשים שחורים, גברים ונשים כאחד. את "הדוגמאות" המעניינות ביותר הוא הוביל אל צלם, שצילם אותן ללא בגדים "משלושה צדדים ובחמישה מצבים". גורלו של ארכיון התצלומים האנתרופולוגי הזה אינו ידוע.