Leela era una guerrera de los Sevateem, una tribu de humanos retrocedidos y salvajes. Conoció al Cuarto Doctor durante la visita que él realizó a su planeta natal, y le ayudó a derrotar a Xoanon. Los dos se hicieron amigos, y cuando le ofrecieron convertirse en la líder de la nueva sociedad de su planeta, se fue con el Doctor. Pese a que él rechazó su propuesta de viajar con él, ella corrió dentro de la TARDIS y se convirtió en su acompañante. (TV: The Face of Evil)
Los orígenes de Leela causaron que ella tuviese pocos conocimientos tecnológicos frente a las maravillas que conocía con el Doctor. Fue educada por él, quien intentó explicarle sobre la naturaleza de sociedades distintas a la suya. En uno de estos viajes conoció a Henry Gordon Jago y a George Litefoot, a quienes volvería a visitar varias veces después. Pese a lo que el Doctor intentaba cambiar en ella, Leela mantuvo su tendencia a ser violenta frente a situaciones amenazantes. (TV: The Talons of Weng-Chiang)
K9 se unió a la pareja en sus viajes. (TV: The Invisible Enemy) Habiéndose enamorado de Andred, un guardaespaldas de la cancillería en Gallifrey, Leela decidió dejar al Doctor y vivir en el planeta de los Señores del Tiempo. (TV: The Invasion of Time) Más tarde se casaría con Andred. (TV: Arc of Infinity)