Erdélyi grófi családból származott, dédapja erdélyi kancellár volt. A Maros-Torda vármegyei Sáromberkén (ma Dumbravioara, Románia) született, magániskolákban tanult. A Debrecenben letett érettségi után Göttingenben és Berlinben hallgatott államtudományt, gazdaságtant, ásványtant, geológiát, földrajzot. Tanulmányainak befejezése után katonai szolgálatba lépett, 1881-től országgyűlési képviselő volt, barátjának tudhatta Rudolf trónörököst, akivel többször vadásztak együtt.

1885-ben Afrikába indult vadászni, és Rudolf, aki szerette volna, ha a Monarchiának sikerül afrikai gyarmatot alapítania, rábeszélte, hogy vigyen magával térképészt, és derítse fel Kelet-Afrika akkor még ismeretlen vidékeit.

Így lett az expedíció tagja a trónörökös jachtján szolgáló pozsonyi Ludwig von Höhnel, akivel Teleki csak 1886 őszén találkozott Zanzibárban. A vidékről egyikük sem tudott sokat, Höhnel helyben tanult meg szuahéli nyelven, és kerített egy tapasztalt vezetőt, aki hallott valamit egy távoli nagy tóról. Amikor 1887 januárjában útra keltek a tengerpartról a földrész belseje felé az expedíció inkább hadjáratnak tűnt, hiszen a 18 tonnányi felszerelést és csereárut 300 teherhordó vitte. Az út még a vártnál is nehezebbnek bizonyult: teherhordóik elszökdöstek, így veszett nyoma a könyveket és térképvázlatokat tartalmazó ládájuknak is. A helyi törzsfőnökök földjén csak bőséges ajándékok ellenében haladhattak át.

Afrika legmagasabb hegye, a Kilimandzsáró lábához 1887 júniusában érkeztek meg, menet közben összetűzésbe keveredtek a vameru törzzsel.

Itt több hónapos pihenőt tartottak, vadásztak, felderítették a környéket. Június 9-én, fittyet hányva az esős időszakra, elindultak a Kilimandzsáró megmászására. Néhány nap alatt az őserdei elefántcsapásokon 2700 méter magasságig jutottak, ezután már nyílt terepen kellett egyre feljebb hatolniuk. A jéghideg eső hátráltatta őket, a két csúcs közti 4220 méter magasan fekvő nyergen már mínusz 11 fok volt. Höhnel 4960 méternél visszafordult, de a kiváló erőnlétnek örvendő Teleki folytatta az utat, és 5310 méternél, első európaiként elérte a hóhatárt.

A hegység 700 méterrel magasabb Kibo csúcsára a német Hans Meyer jutott fel elsőként két évvel később.

Készleteiket feltöltve július végén indultak tovább. Viszonylag békés körülmények között haladtak át a maszájok területein. Teleki itt varázsló hírébe keveredett, mert rakétákkal esőt csinált, és ennek a hírnevének később nagy hasznát vették. A harcias kikujuk földjén viszont már folyamatosak voltak az összetűzések, de a puskák biztosították számukra a fölényt. Teleki végül valóságos büntetőexpedíciót indított.

50 falut gyújtatott fel, ezernél több állatot hajtatott el, ezután békén hagyták őket.

Teleki 1887. október 17-én az 5200 méter magas Kenia (Kenya) hegy megmászására indult, a hidegben 4680 méterig jutott, magasabbra, mint addig bárki más. Az expedíció a hónap végén elérte az addig ismert terület határát, innen térkép nélkül kellett tovább menniük. Az indulás előtt Teleki rengeteg állatot ejtett el, hogy biztosítsa élelmüket. Az ismeretlen, sivatagos vidéket átszelve a Baringo-tó mentén, a Nyiro hegy lábát megkerülve keresztezték az Egyenlítőt. Út közben négy emberük szomjan halt. Felfogadott vezetőiket követve 1888. március 10-én első európaiként pillantották meg a bennszülöttek körében csak Fekete-tóként emlegetett titokzatos tavat.

A világ legnagyobb állandó sivatagi tavát, Afrika ötödik legnagyobb belvizét Rudolf trónörökösről nevezték el, ma Turkana-tó a neve.

A közelben egy alig 600 méter magas, működő tűzhányót is találtak, amelyet Höhnel Telekiről nevezett el, a lúgos vízű tó déli partján pedig egy tűzhányó Höhnel nevét kapta. A sivár tájon tovább haladva jutottak el a bennszülöttek körében ismert kisebb, sós vizű tóhoz, amelyet Rudolf feleségéről Stefánia-tónak neveztek el (ma Csev-Bahir). Az esős évszak közeledte és teherhordóik ellenkezése miatt innen visszafordultak, és nagy nélkülözések, éhezések közepette 1884. október 24-én érkeztek meg az Indiai-óceán partján fekvő Mombasába.

Az út során háromezer kilométert tettek meg Afrika ismeretlen részén, gazdag állat-, növény- és néprajzi gyűjteménnyel, jelentős fotóanyaggal tértek haza, ők voltak a tudományos fényképezés úttörői.

Teleki, aki a költségeket magánvagyonából fedezte, csak egy rövid cikket publikált az expedícióról, a részletes történetet Höhnel írta meg. Ők ketten jó barátok maradtak, Teleki minden évben vendégül látta Höhnelt Sáromberkén. Teleki 1893-ban Indiában, Jáván, Szumátrán és Borneón is járt, 1895-ben ismét megkísérelte a Kilimandzsáró megmászását. Munkásságért számos kitüntetést kapott, 1894-ben a Magyar Tudományos Akadémia tiszteleti tagjának választották, 1897-ben valóságos belső titkos tanácsosi címet kapott. 1916. március 10-én Budapesten halt meg és Sáromberkén, a családi kriptában helyezték örök nyugalomra. A 19. század nagy magyar Afrika-utazójának nevét Érden általános iskola, Kenyában turistaház, tengerszem és több növény viseli.