In het begin van 1856 bezocht hij opnieuw Oost-Soedan, verkende de Bajudasteppe reisde door de kuststaten van de Rode Zee waaronder [[Somalië]]. In 1857 keerde hij om gezondheidsredenen terug naar Europa. Hier bleef hij tot eind 1860 en ordende in die periode zijn verzamelde [[specimen]]s en beschreef zijn reizen.
inIn 1860 werd hij door [[August Petermann]] en [[Heinrich Barth (ontdekkingsreiziger)|Heinrich Barth]] aangesteld als leider van een expeditie, die moest onderzoeken wat er was gebeurd met de sinds 1855 vermiste ontdekkingsreiziger [[Eduard Vogel]]. [[Alexandrië]] was het vertrekpunt voor de reis naar [[Sultanaat Ouaddaï|Ouaddaï]], waar Vogel was zoek geraakt. Heuglin vreesde echter dat Vogel vermoord was in een gebied waar hij en zijn expeditieleden grote kans hadden op hetzelfde lot. Daarom besteedde hij meer aandacht aan wetenschappelijke activiteiten dan aan zijn formele zoekopdracht en bereisde andere gebieden.<ref>{{de}}{{Citeer web |url=http://www.heuglin-schule.de/ths/cms/front_content.php?idcat=48&lang=1 |titel=Biographie von Theodor Heuglin |uitgever=website Theodor Heuglin-Schule |bezochtdatum=28 maart 2014}}</ref> Op 17 juni 1861 bereikte de expeditie [[Massawa]], bleef tijdens het regenseizoen in het nabijgelegen hoogland en ging vervolgens niet richting Khartoem, maar zij maakten een omweg door [[Gondar]] in Ethiopië. Op 4 april 1862 bezocht Heuglin de keizer [[Theodorus II van Ethiopië]]. Daarna werd Heuglin officieel ontheven van zijn functie als expeditieleider. De resultaten van deze expeditie zijn vervat in een boek dat in 1864 werd uitgegeven.
In 1863 sloot Heuglin zich samen met onder andere Hermann Steudner aan bij het reisgezelschap van de steenrijke Nederlandse avonturierster [[Alexandrine Tinne]]. Dit gezelschap reisde naar het zuidwesten van [[Soedan]] door [[Western Bahr el Ghazal]] over de Bahr el Ghaza, een zijrivier van de Witte Nijl. Onderweg overleden de moeder van Alexandrine, Henriette Marie Louise van Capellen en Steudner; Heuglin werd ziek. Hierop besluit het gezelschap om terug te keren naar Khartoem, om vervolgens terug te reizen naar Europa.
