Höhnel sorhajóhadnagy 1886 novemberében érkezik Zanzibárba, az expedíció indulási helyére, Teleki pár héttel később. Itt három hónapot töltenek előkészítéssel, megfelelő mennyiségű és minőségű teherhordó, öszvérhajcsár toborzásával. Komoly fegyveres őrséget szerveznek annak ellenére, hogy Teleki a bennszülöttekkel szemben a mosolypolitikát kívánta alkalmazni. Az expedíció 17 tonnányi felszerelését 470 csomagra osztották szét, melynek jelentős része a bennszülötteknek felajánlható ajándék és csereáru. Itt hallanak először az ismeretlen tavakról, melyeket célpontjukul tűztek ki. A tóvidék a még feltérképezett Baringo tavon túl volt, ezért lett az expedíció jelszava "Baringo na mbele kidogo" azaz "A Baringohoz és még valamivel tovább".

A 283 főből és 25 szamárból álló karaván 1887. január 23-án kezdte meg útját a Star gőzösön Panganiba hajózva. Itt további száz fő csatlakozik a karavánhoz. A tengerparttól február 4-én távolodnak el. Az út ezen első szakaszán már csőstől jelentkeznek a gondok, a szedett-vedett társaságból sokan próbálnak szökni, sokukat meg sem találják. A maradék lerészegedik, fegyveres összetűzésekre is sor kerül, de Teleki tartózkodik a büntetéstől. Az uszambara fővárosban az utazót fogadja Moszindében Szembadzsa szultán "királyi fészerében", vele azonban Teleki n

em tud kereskedni. Pár hetes út után érkeznek el Tavetába, ahol három hónapos szünetet tartanak. A Kilimandzsáró lábánál fekvő város a vadászok és kereskedők Mekkája. Az időt vadászattal, kirándulással töltik, olyannyira, hogy az esős évszak dacára Teleki és Höhnel június 9-én a Kibo megmászására indul. A jobb erőnlétű magyar egészen 5310 méterig jut el, de a csúcsig ő sem ér fel. Így is ő az első ember, aki idáig feljut. Készleteiket feltöltve július 25-én indulnak tovább. A szökések száma csökken, de Höhnel beteg lesz, amely betegsége többé-kevésbé az út végéig kínozza. A harcos természetűként ismert maszaiokban kellemesen csalódnak, kapcsolatuk békés, a cserekereskedelem végre virágzik. A bennszülöttek között Teleki nagy tekintélyre tesz szert, "leibon"-ná, varázslóvá válik, amikor rakétáit eregetve esőt csinált. Esőcsináló hírneve később is hasznos lesz, mivel hírük gyakran megelőzi őket. Jó vadászterületeken haladnak át és Teleki vadászpuskájával egyedül látja el a 300 fős expedíciót friss hússal. Höhnel állapota egyre rosszabb, már hordágyon utazik. Augusztus végére értek el a Ngongo bagaszhoz (Ngongo patak), amely a békés maszaiok és a valóbán harcias kikujuk határa. Az elkövetkező hónapban fegyverüket kéznél tartva haladtak, három összecsapás volt a csapat és az azt követő 1-2 ezer harcos között több száz (bennszülött) halottal. Az ellenségeskedéseknek csak akkor lett vége, amikor Teleki, minden ellenérzése ellenére elrendeli a büntetőexpedíciót. A megregulázott bennszülöttek ezután már a cserekereskedelemre is hajlandóak voltak. Október elejére érik el a Kenya-hegy lábát, amely megmászására Teleki 17-én indul. Ismét nincs szerencséje, 4680 méterig jut fel (ezt az eredményt később többen is kétségbe vonták). A hegy alatt fekvő Ndoroból a karaván kettéválva haladt tovább, Teleki egyenesen a Baringóhoz, Höhnel a Guasszó Nyiro (Nyiró patak) alsó folyásához tartott. December hetedikén egyesül a csapat a Baringo-parti Nyemszben, amely útjuk utolsó ismert, feltérképezett állomása. Ötven napot maradnak itt, amit a készletek feltöltésére, a kimerült, alultáplált csapat feljavítására fordítanak. Teleki számára itt már megszűnik a vadászat szórakozás jellege, többtonnányi vadad ejt el étkezési célra, noha az elefántcsontot sem veti meg. Höhnel állapota ismét válságosra fordult, január 24-én majdnem meghal. Az egész expedíciót foglalkoztatja az előttük álló ismeretlen, Teleki megírja utolsó levelét a trónörökösnek, melyben többek között Höhnelt a figyelmébe ajánlja.

Három útvonal közül választhatnak, hosszú tárgyalások után a keletit választják.

A nagy ugrást, a hat hónapos térkép nélküli bolyongást 1888. Február 10-én kezdi a "Safari a pálé, a pálé" azaz a "mindenre kész karaván".

Elérik a Nyiró-hegységet, ahol a burkenadzsi törzsből vezetőket fogadnak. A Baringót és a Basszó Narokot (Fekete később Rudolf-tó) végül mindössze 26 nap alatt érik el. Telekit meglepi a gyors siker, de rá is jön az eddigi sikertelenség okára; a két tavat elválasztó lakatlan, száraz vidék a sós vizű tó partján sem változik meg, ezért szinte lakhatatlan, áthatolhatatlan. Az expedíció itt veszíti el öt tagját. Mivel a tó partján szinte semmilyen növényzet sincs a marhákat márc. 16-án kénytelenek leölni. Nagy a szárazság, a menet szomjazik. Hogy az unalmat elkerüljék a forró, száraz időt hideg, nedves váltja fel, a folyók, a tó kiáradnak, Telekinek el kell hagynia a tó partját. 

Április 7-ére érték el az északi partot, ahol az ismeretlen, de barátságos resiatokkal találkoztak. Negyvenöt napos tartózkodásuk a barátságos vidéken igazi ajándék volt az elcsigázott csapat számára. A tizedik napon Teleki a csoport nagyobb részét hátrahagyva a Basszó na Eborhoz (Fehér majd Stefánia-tóhoz) indult. Amit talált nem volt túl bizalomgerjesztő, egy kiszáradóban lévő sós tó félsivatagos vidéken, mégis örömmel keresztelte meg a helyszínen készített "pezsgővel", mely méz, víz, borkősav és szódabikarbóna keverékéből állt. Még himnuszt is írtak a nagy esemény tiszteletére, melynek éneklésétől a főtáborba visszavezető úton még egy homokvihar sem tudta kedvüket elvenni.

Itt azonban újabb problémával álltak szemben: Merre tovább? Az expedíció jellegéből adódóan a nyugati oldalt kellett volna választani, de ennek ellent mondott a lassan beköszönő esős évszak és a bennszülöttek ellenkezése. Teleki nem akart összetűzést az egyébként nagyon vendégszerető resiatokkal és féltve a legénységet, a biztosabbnak tűnő keleti oldalt választotta a visszatérésre. A felkészülés azonban nehezen ment, mivel nem tudtak elég élelmet és teherhordó állatot szerezni és már nyakukon volt az áradás. Május l4-én elindultak, a nehéz terepen a rossz körülmények ellenére a csapat annyira próbált igyekezni, hogy a tó déli csücskéhez vezető útra elég volt tizenhat nap! Innen letértek a már megismert útról és a tavat délről megkerülve haladtak tovább.

Ekkor fedezik fel az éppen működő, állítólag addig névtelen Teleki-vulkánt. A szuk és turkána bennszülöttek országán keresztülhaladó expedíció sem vadászatból, sem kereskedelemből nem tud élelmiszert szerezni magának, már szinte éhen hal, ezért Teleki kénytelen rabló hadjáratot szervezni a Kerio folyó mentén. Nyolcnapi kemény dzsungel után július 29-én érkeznek vissza Nyemszbe a Baringóhoz. Innen Taveta érintésével a leggyorsabb és legrövidebb úton tértek vissza a tengerpartra, Mombassaba. Két nap pihenő után áthajóztak Zanzibárba, ahol két hónap telik el az utólagos tennivalókkal. Kifizetik a béreket, eladják az elefántcsontot, amely a mintegy százezer forintot felemésztő vállalkozás 25-30%-át fedezi. Teleki felvetve a két tó északról való megközelítésének ötletét, ó-etiópiai kirándulás tervét gondolja ki. Ádenbe hajóztak, majd 15 napnyi unalmas sivatagi lovagolás után tíz szintén unalmas napot töltöttek Harar szent városában, ahol Teleki értesül a Mayerlingi-tragédiáról, fő patronálójának haláláról. Itt határozza el expedíciójának befejezését. A hazaúton Kairóban mindkettőjüket a Geográfiai Társaság tiszteletbeli tagjává választják. Teleki London érintésével tér haza.

Nevezetes utazásait Höhnel írta meg két kötetes művében: „A Rudolf- és Stefánia-tavakhoz”, amely magyar, német és angol nyelven jelent meg.