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) látta meg a napvilágot, iskoláit magánúton végezte. 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: 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, s 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 két év múlva a német Hans Meyer jutott fel.)
Készleteiket feltöltve július végén indultak tovább, s 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, e 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.
Az expedíció dicstelen része, hogy Teleki végül valóságos büntetőexpedíciót indított a törzs ellen,
különleges kegyetlenséggel 50 falut gyújtatott fel, ezernél több állatot hajtatott el, s ezután békében hagyták őket.
Teleki 1887. október 17-én az 5200 méter magas Kenia (Kenya) hegy megmászására indult, s a hideg időben 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 által 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 által emlegetett 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, annak részletes történetét Höhnel írta meg. Ők ketten jó barátok maradtak, Teleki minden évben vendégül látta Höhnelt Sáromberkén.
Höhnel és Teleki közös útjairól 1891-ben jelent meg könyv, amelyet online is fellapozhat.
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á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.
Az MTI Sajtóadatbank portréja.