Teleki Sáromberkén (ma Dumbravioara, Románia) született. A göttingeni és a berlini egyetemen állam- és gazdaságtudományt, mellette ásványtant, geológiát és földrajzot tanult. 1881-től országgyűlési képviselő volt. Közeli barátságba került Rudolf trónörökössel, akivel számos utazáson vett részt. 1886-1889 között mintegy 3000 kilométeres kelet-afrikai utat tett meg Ludwig von Höhnel társaságában Afrika akkor még ismeretlen vidékén. Első európaiként érte el a Kenya-hegységben a hóhatár magasságát (4680 m.), felfedezte a Rudolf- (ma Turkana-) és Stefánia-tavakat, valamint a ma is a nevét viselő vulkánt. Nagy állat- és növénygyűjteménnyel tért haza. 1893-ban Indiában, Jáván és Szumátrán, 1895-ben ismét Kelet-Afrikában járt. Megpróbálta megmászni a Kilimadzsárót, de a csúcsig nem jutott fel. Igen sok fényképet készített, ami akkoriban még különleges tevékenységnek számított. Afrikai kutatóútjának történetét Höhnel írta meg.