1886 őszén Höhnel Lajos kíséretében Afrikába utazott és 1887 tavaszán nagyobb felfedező utat tett. Január 23-án nagy karavánnal hagyták el Zanzibárt, s tavasszal értek el a Kilimandzsáró haváig, melyen Teleki az utazók közt elsőnek hatolt fel az örök hó határáig. Újból szervezve 250 főnyi karavánját, októberben a Kenya-hegyet mászta meg; nagyobbrészt ismeretlen vidékeken keresztül mentek a Baringo-tóig, s onnan tovább hatolva, 1888 tavaszán két nagyobb tavat fedeztek fel, melyeket Teleki Rudolf- és Stefánia-tavaknak nevezett el. A Rudolf-tó partjához közel fekvő 630 m magas működö vulkánnak Höhnel a Teleki-vulkán nevet adta. 1888 november 25-én megérkeztek Mombaszába, ahonnan Teleki 1889 tavaszán jött vissza Magyarországra.

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 nem 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.