While growing up in a typical Moscow family, he dreamed of becoming a war-plane pilot, which was a very common desire of many boys of the World War II period. This is also often attributed to the fact that his father worked in an airplane factory. During the Great Patriotic War he and his whole family worked in a weapon manufacturing/aviation factory. After the war, he joined the Moscow Art Theatre school, where he studied under Mikhail Yanshin.
In his first film, Leonov was cast as an extra and did not receive any recognition. He later became Georgiy Daneliya's regular, appearing in all of his features, including Gentlemen of Fortune, Autumn Marathon, Mimino, Afonya and Kin-dza-dza!. According to the Allmovie, "his short, round stature, expressive eyes, broad and open face, slow movements, and slightly slurred speech made him ideal for the comic roles in which he specialized". But he also attracted critical notice for his tragic parts and the invariable naturalness of his acting. Many notable actors were said to avoid appearing in the same films with Leonov, for his natural manner of acting made them seem strained.
Despite Leonov's brief appearance in Daneliya's Autumn Marathon (1980) (one of his most popular films), the role won him the Best Actor at the Venice Film Festival. In Autumn Marathon, it is said, Leonov brilliantly demonstrates the typical Leonov anti-hero. He gave a hilarious portrayal of a simple, nosey man who drank too much and who adored nothing more than talking nonsense as long as anyone could stand it. Among the other films he was instrumental in raising to the classic level were Gentlemen of Fortune and Belorussian Station, both made in 1971. Like all of Leonov's movies, they are frequently rerun on television. Reportedly, "Leonov was to Russians what Fernandel was to the French." He performed over 200 roles and was the Russian cinema's best-known supporting actor.
In 1991 (or in 1988), when touring in Germany, he suffered a massive heart attack, which put him into a coma for 10 days (or 16 days). His life was saved only after major surgery and Leonov recovered – only to begin a schedule of performances at the Lenkom Theatre.
In 1993, a year before his death, Leonov was asked during a film festival "What years in the Russian theatre's life were the most productive?" Leonov replied:
Life has flown so quickly that it is hard to identify any one period. But I shall never forget the famous artists of past years, my teachers: Diky, Mikhail Chekhov, the young Simonov, Pevtsov, Rusinova, Vakhtangov, Gritsenko and Yakovlev. I saw the bloom of the Art Theatre. In 1941 I, then a boy, hanging somewhere on a chandelier, saw the Three Sisters where three beautiful women were dreaming about some new fine life. I shall never forget Anna Karenina with Tarasova. At that time people played cordiality, kindness, laughing through tears and leaving a bit of their heart on the stage. To achieve profundity, there is a need for skill, but skill comes solely through suffering. Once Pevtsov, sitting in a kitchen with Nikolai Simonov, told him: "Kolya, beware of indoor organics.' But now the very aesthetics have changed. "Indoor organics" have turned into art everywhere. And also, there is no literature. Last century forty writers overturned the world. Today there are hosts of them, but literature is no longer what it used to be. The theatre must stage Plays spelled with a capital letter. But we give preference to effective staging, forgetting all about feelings and passion – not necessarily loud passion. Passion can be quiet. At one theatre I was once told: "Leonov, come to work with us. We are rich and spend nearly all our time abroad." "Why, is your theatre so strong?" I asked. "No, our exchange is strong." The exchange trades in timber and joins the theatre carriage to its freight train. And as to the festival – may God permit it to take place. If money has been found.
Leonov died on 29 January 1994 on his way to the Lenkom Theatre to perform in The Prayer for the Dead (A Memorial Prayer). When his death was announced in the auditorium, the audience spontaneously flooded into the church across the road and lit candles in mourning. Over half a million people turned out in freezing conditions for a procession to a memorial service. He is buried in Novodevichy Cemetery in Moscow near other outstanding figures of Russian culture.