В возрасте 22 лет Евгений дебютировал на киноэкране – режиссер Владимир Немоляев (отец актрисы Светланы Немоляевой) пригласил его сняться в музыкальной комедии «Счастливый рейс», главными звездами которой были Николай Крючков и Михаил Жаров. Поскольку Евгений искал тогда любой приработок, то согласился. Дебют получился удачным, но активно сниматься Леонов начал с 1955-го, когда сыграл яркие роли шофера-пройдохи Снегирева в фильме «Дело Румянцева» И. Хейфица и Пашки Еськова в «Дороге» А. Столпера. А по-настоящему открыла зрителю Леонова блестящая комедийная роль «дрессировщика», а на самом деле буфетчика Шулейкина в «Полосатом рейсе» В. Фетина (1961). Своего героя-прохвоста Леонов сделал обаятельным, милым и смешным, его злоключениям зрители искренне сочувствовали и одновременно смеялись над Шулейкиным. В итоге «Полосатый рейс» занял первое место в прокате года и до сих пор остается одним из любимейших советских фильмов. В дальнейшем актера активно приглашали сниматься в комедиях. Сейчас трудно представить без Леонова такие фильмы, как «Тридцать три» (1965), «Зигзаг удачи» (1969), «Джентльмены удачи» (1971), «Большая перемена» (1972), «Афоня» (1975), «Обыкновенное чудо» (1978), «Осенний марафон» (1981), «Кин-дза-дза» (1986), «Убить дракона» (1988). Не во всех из них Леонов играл главные роли, но его персонажи всегда запоминались зрителю и, что называется, мгновенно «уходили в народ». Многие фразы, произнесенные Леоновым с экрана, становились пословицами: «Украл, выпил – в тюрьму!», «Пасть порву, моргалы выколю» («Джентльмены удачи»), «Здравствуйте, я король» («Обыкновенное чудо»), «Хорошо сидим», «Не обратно же выливать» («Осенний марафон»). Интересно, что для экрана Евгений Павлович практически не гримировался – у всех его героев была его собственная простецкая внешность: лысина, нос картошкой, лукавые маленькие глаза, пухлые губы и щеки, характерный глуховатый говорок. Но в итоге и матерый бандит, и сказочный король, и инопланетянин в исполнении Леонова смотрелись великолепно. Актер был Личностью с большой буквы, и это чувствовалось всегда…
Особенно много Леонов снимался у Георгия Данелия («Тридцать три», «Не горюй!», «Афоня», «Мимино», «Осенний марафон»; в «Джентльменах удачи» Данелия был автором сценария). «Мне всегда хорошо работается с Данелия, – говорил сам актер. – Атмосфера доброты и доверия, а главное, он работает, ощущая целое. Мы можем ошибиться и переснять, но он примечает то, что дает возможность копать глубже, хоть это и сложно. И мы опять и опять пробуем, но у меня никогда не было ощущения тупого угла – мол, это сделать невозможно. А у некоторых других режиссеров все время попадаешь в тупик – это не годится, то не нужно…»
За комедийными возможностями Леонова зрители и режиссеры не всегда видели в нем драматического артиста. Но когда позволял сценарий, Леонов блестяще умел быть на экране трогательным, серьезным, взволнованным. Впервые удивил всех «комик» Леонов в мелодраме В. Фетина «Донская повесть», где артист с блеском сыграл казака Якова Шибалка. А потом были «Белорусский вокзал» (1970), «Премия» (1974), «Старший сын» (1975), «О бедном гусаре замолвите слово» (1980), «Время и семья Конвэй» (1984).
Много и с удовольствием работал Леонов и в озвучании. Его шедевр – закадровый голос Винни-Пуха (серия мультфильмов Ф. Хитрука, 1969–1972). Причем поначалу голос актера не устраивал никого, включая самого Леонова, но потом звукоинженер предложил немного ускорить запись, и «Винни-Пух» был «найден». Другой классической работой Леонова в анимации стал блистательный мультфильм Л. Носырева «Волшебное кольцо» (1979), в котором Евгений Павлович перевоплощался в помора-сказителя.