מורו לשעבר ייעץ לו לעבור לאוניברסיטת היידלברג. כמו באוניברסיטאות אחרות בגרמניה, גם שם אזרחי רוסיה לא היו צריכים להציג תעודות לימודים. למרות מצבה הכלכלי הקשה של המשפחה, אמו הסכימה לשלוח אותו לגרמניה. במרץ 1864 חלה מיקלוחה בדלקת ריאות ובנוסף לכך בדלקת שלפוחית. ב-21 באפריל 1864 נסע ניקולאי לגרמניה.
שנות הלימודים.
היידלברג ולייפציג.
בהיידלברג נרשם מיקלוחה להרצאות בנושא גאומטריה וטריגונומטריה, אך השתתף גם בקורסים בכלכלה פוליטית, היסטוריה מודרנית, מדינה ומשפט, מה שהכעיס את אמו. תנאיו החומריים היו דלים, הכסף שנשלח לו מסנקט פטרבורג הספיק בקושי לשכר לימוד ולדירה. בשל חששות מהטרדות המשטרה הרוסית, בעצת אמו לא חזר לרוסיה ונסע במהלך החופשה הראשונה ליער השחור כדי לשפר את בריאותו. לפי האוטוביוגרפיה שלו בסמסטר החורף של השנה האקדמית 1864/1865 הוא למד פיזיקה, כימיה, גאולוגיה, פילוסופיה, משפט פלילי ואזרחי בהיידלברג. הוא נסחף אחר הסוציאליזם האוטופי, בעיקר אוון, סן-סימון וצ'רנישבסקי, שאת הרומן שלו, "מה לעשות?", הביא איתו מסנט פטרסבורג. עם זאת, תבוסת התנועה הדמוקרטית ברוסיה בשנות ה-60 של המאה ה-19 הביאה לכך שהתלמידים הרוסים בגרמניה התפצלו. המתונים חזרו לרוסיה והשתלבו שירות המדינה, והרדיקלים עברו לשווייץ, עם התגברות תגובת המשטרה בדוכסות הגדולה של באדן. עד שנת 1866 כמעט ולא נשארו סטודנטים רוסים בהיידלברג.
מיקלוחה בילה את סמסטר הקיץ של שנת 1865 באוניברסיטת לייפציג, שם נכנס לפקולטה הקאמרלית , שהכשירה מומחים לעבודה כמנהלים בחקלאות וייעור. מיקלוחה הצטרף לפקולטה ב־19 באפריל 1865, והשתתף בארבעה קורסים: גאוגרפיה פיזית; תיאוריות של כלכלה לאומית, סטטיסטיקה השוואתית ומחקרי מדינה בגרמניה; תולדות הפילוסופיה היוונית ותורות על עצמות וגידים. לאחר שנכנס לפקולטה ה"יישומית" לבקשת אמו, הוא המשיך ללמוד מדעים שונים. באוקטובר 1865 עבר ניקולאי לעיר ינה, שמשכה אותו הן בזכות עלות המחיה הנמוכה והן בזכות העובדה שהאוניברסיטה המקומית הפכה למרכז הדרוויניזם בגרמניה.
ינה.
ב-19 באוקטובר 1865 הגיש ניקולאי פון מיקלוחו (כפי שכינה את עצמו) בקשת קבלה לפקולטה לרפואה של אוניברסיטת ינה שבדוכסות סקסוניה-ויימאר-אייזנך. בנוסף לקורסים ברפואה, ניקולאי שילם גם על הרצאות ביסודות החקלאות, האסטרונומיה והטלגרפיה, אולם בהמשך התמקד במקצועות ליבה במשך שלוש שנים. קארל הגנבאוור וארנסט הקל הפכו למנחים של מיקלוחה באוניברסיטת ינה. כבר במכתבים ממרץ 1866 מכנה הקל את מיקלוחה "עוזרו הנאמן והשימושי". אף על פי שלא עבד בתמורה לשכר, עבודותיו סיפקו לו ניסיון רב. ניקולאי הכין עזרים חזותיים להרצאותיו של הקל, הכין עבורו טבלאות וצייר תצפיות מיקרוסקופיות. בעקבות עבודה ממושכת עם מיקרוסקופ, במרץ 1866 לקה מיקלוחה ב"שיתוק קל של החצי השמאלי של פניו". הקל כתב להוריו כי עליו לדאוג לסטודנט רוסי שאין לו אף אחד בגרמניה.
באותה העת היה נהוג בגרמניה לפגוש בנשים באמצעות התכתבות במודעות העיתונים. התכתבויות כאלה יכלו להוביל להכרות מרחוק ואפילו לנישואין. עדות ראשונה להתכתבויות כאלה מצד מיקלוחה היא משנת 1865. המטרה העיקרית עבורו, ככל הנראה, הייתה בקיאות בז'אנר כתיבת המכתבים הגרמני. כמה דוגמאות של מכתבים כאלה שרדו, ועל פיהן ניקולאי כתב בנימה אירונית ואפילו בתחושת עליונות. בשנת 1868 ניהל מיקלוחה רומן עם אורליה, בתו של הפרופסור לסטטיסטיקה ברונו הילדברנד. במהלך העיסוק הקליני התרחש רומן בין ניקולאי למטופלת שלו, וזו הורישה לו את גולגולתה לפני מותה. ניקולאי יצר מהגולגולת מנורת שולחן. מנורה זו שימשה אותו בכל מסעותיו והייתה עדיין קיימת בשנת 1887.
המשלחת לאיים הקנריים.
במרץ 1866 השלים המנחה של ניקולאי, ארנסט הקל, את המונוגרפיה "המורפולוגיה הכללית של האורגניזמים". כשמאס בעבודה המשרדית, החליט לנסוע לסיציליה כדי לחקור את החי הימי בים התיכון. המשלחת כמעט בוטלה בגלל פרוץ מלחמת אוסטריה-פרוסיה, בה השתתפה דוכסות סקסוניה-וויימאר-אייזנך (שהעיר ינה הייתה חלק ממנה). לאחר סיום המלחמה החלה מגפת כולרה בדרום אירופה, שבגללה הופסקה התעבורה הימית ונסגרו הגבולות. רשויות מסינה, שהייתה יעד הנסיעה של הקל, הודיעו כי יירו לעבר כל ספינה שתתקרב לנמל. בעקבות זאת הוא נאלץ לשנות את תוכניתו.
בסוף אוקטובר 1866 יצא ניקולאי יחד עם סטודנט נוסף, הרמן פול, ברכבת לבורדו, ומשם בדרך הים לליסבון. בזכות ציור של ניקולאי ידוע שביקרו גם בסינטרה. הקל, יחד עם הפריבט-דוצנט ריכרד גרף, הפליג לליסבון דרך אנגליה, שם עמדו לפגוש את תומאס האקסלי ואת דרווין בעצמו. ב-15 בנובמבר הפליגו אנשי המשלחת למדיירה. הקל התכוון לערוך שם היכרות ראשונית עם עולם החי של הים הפתוח ושל אזור הכרית באוקיינוס האטלנטי, ולאחר מכן להפליג לאיים הקנריים. עם זאת, התברר שהתחבורה לאיי מדיירה הופרעה בגלל כולרה, ולאחר שהייה של יומיים בפונשל, הנוסעים הגיעו ב-22 בנובמבר לסנטה קרוס דה טנריפה.
ב-9 בדצמבר עגן הצוות בנמל ארסיפה באי לנזרוטה. בנמל הם התחילו בפעילות מדעית: חקר מדוזות, סרטנים ורדיולריות שחיו בשכבת מי השטח נאספו ברשת, כמו גם דוגמאות לעולם החי של הקרקעית. הסטודנט מיקלוחה חקר ספוגיים וכתוצאה מכך גילה סוג חדש של ספוג פחמי, וקרא לו "Guancha blanca"לכבודם של תושבי האיים הילידים. דגימות של דגים נקנו לרוב מדייגים בשוק, וכתוצאה מכך אסף מיקלוחה נתונים על שלפוחית השתן של דגים ועל מוחם של כרישים.
התושבים המקומיים נזהרו מהזואולוגים הגרמנים, וחשדו שהם מרגלים פרוסים או מכשפים. השמועה האחרונה הובילה לכך שהקל התבקש באופן קבוע לרפא מחלות ולחזות את העתיד. הבית ששכר הצוות שפע חרקים וחולדות; הקל חישב כי בינואר 1867 בלבד הוא הרג יותר מ 6,000 פרעושים. לבסוף הוחלט לחזור לאירופה, אך ניתן היה לעשות זאת רק דרך מרוקו. ב־2 במרץ הגיעו הקל וגרף למרוקו על סירה אנגלית. מיקלוחה ופול החליטו לטייל במרוקו: לאחר שקנו תלבושות ערביות ושכרו מדריך-מתורגמן, הם הגיעו בשיירה למרקש, שם התעניין ניקולאי במיוחד בחיי הברברים. לאחר מכן נסעו המטיילים לאנדלוסיה. במדריד ניקולאי ביקר במחנה צוענים, וגם חלה מאוד. משם המשיכו לספרד, הם בילו שבועיים באלחסירס וחקרו את החי הימי. הם המשיכו ברכבת לפריז, שם ביקרו בתערוכה העולמית, ובתחילת מאי 1867 חזרו לינה.
בחירת מסלול החיים.
בשנת 1868 סיים מיקלוחו-מקלאי את לימודי הפקולטה לרפואה באוניברסיטת ינה. מכיוון שהוא לא התכוון להיות רופא מטפל, לא ניגש לבחינות הממלכתיות. בקיץ 1868 התפרסם מאמרו השני - "חומרים להכרת ספוגים", שתיאר מין חדש של ספוג. ביולי 1868 כתב את מאמרו השלישי, "לקראת אנטומיה השוואתית של המוח" על בסיס חומריו על מוח הכרישים, בו תיאר את הבנתו במנגנון האבולוציה. בניגוד למוריו דרווין והקל, שטענו למאבק על הקיום, הוא העדיף את מודל הבידול - מעבר מהצורה המקורית לצורות אחרות, לאו דווקא מתקדמות יותר. קארל בר , הסמכות בנוירופיזיולוגיה, הסכים עם רעיונותיו של מיקלוחו. עם זאת, התזות העיקריות שלו, הן ביחס לבידול והן לתפקיד שמשחק בתיאוריה זו מוח הדגים, לא נשתמרו במדע.
באפריל 1868 ביקר ניקולאי בגותה, שם נמשך במיוחד למערכת כתב-העת הגאוגרפי של הקרטוגרף הנודע אוגוסט פטרמן. המדען הצעיר התעניין במחקר גאוגרפי, במיוחד באזורים שנחקרו מעט באופן יחסי. הוא למד מפטרמן על מסע הקוטב הגרמני הראשון ואף רצה לקחת בו חלק, אך סורב. גם חוקר הקטבים השוודי, אדולף אריק נורדנשלד, סירב לבקשתו. במקום זאת, מיקלוחו החליט לערוך מסע לסיציליה, אולם באותה תקופה לא היה לו כסף אפילו לדיור. בקיץ הוא שלח מכתבים רבים לאחיו סרגיי, וביקש ממנו להשפיע על אמו, כשהוא מתלונן על בריאות לקויה וחוסר כסף.
המשלחת לסיציליה.
את המסע לסיציליה בשנת 1868 יזם אנטון דורן, זואולוג-דרוויניסט ותלמידו של הקל. ב־2 באוקטובר הגיע מיקלוחו-מקלאי למסינה, שם שכר חדר במלון זול. עד מהרה הוא הצליח לגלות סוג חדש של ספוג, אותו קרא על שמו של מורהו "Astrospongia Heckelii". דורן הגיע באמצע אוקטובר; בהיותו בעל באמצעים הוא שכר כמה חדרים בארמון פאלאצו ויטאלה. בארמון הותקנה מעבדת שדה, שם חקר דורן סרטנים, ומיקלוחו עסק במורפולוגיה של ספוגים ואנטומיית מוח של דגים. דורן בנה במעבדה אקווריום עם מים זורמים והתחקה לראשונה אחר מעגל התפתחותו מהזחל של הלובסטר achelata .
המשלחת לים סוף.
בפברואר 1869 נודע למיקלוחו על השלמת תעלת סואץ. הוא החליט לנצל את ההזדמנות האחרונה לתאר את החי הימי של ים סוף, שבימים ההם כמעט ולא היה מתועד, לפני שיחובר אל הים התיכון. ב-12 במרץ 1869 הפליג ניקולאי לאלכסנדריה. ב־22 במרץ עזב את קהיר לכיוון סואץ. שם הוא חווה את ההתקף הראשון של מלריה - מחלה שתלווה אותו עד סוף ימיו. על פי תקופת הדגירה נראה שהוא נדבק כבר בסיציליה, שם המחלה הייתה נפוצה.