Дебютировал в профессии на сцене московского театра им. Станиславского. Известность к актеру пришла после исполнения роли Лариосика в пьесе «Дни Турбиных» и главной роли в картине  «Полосатый рейс». А потом были «Тридцать три»,  «Белорусский вокзал», «Джентльмены удачи», «Осенний марафон», «Большая перемена», «Старший сын», «Афоня» и другие, принесшие ему огромную зрительскую любовь и профессиональное признание. Режиссер Георгий Данелия считал Леонова своим талисманом и не представлял своих фильмов без его участия.  Несмотря на «неактерскую» внешность, творческий диапазон Леонова был необычайно велик, он был заметен в любой, даже самой небольшой роли.