Именно эта роль повлияла и на кинокарьеру Папанова. Все, что актер делал в кино до сих пор, выстроилось в список ролей, не имевших особого успеха, малозаметных, неинтересных, а то и вовсе несостоявшихся. Например, молодой режиссер Э. Рязанов пробовал его на роль Огурцова в «Карнавальной ночи». Однако предпочел И. Ильинского. В 1960 г. он же предложил Папанову сняться в фильме «Человек ниоткуда», но уже готовая работа по прихоти чиновников (якобы по указанию самого М. Суслова) так и не увидела премьеры. Фильм показали зрителям только через 28 лет, уже после смерти А. Папанова. И когда актер для себя уже решил, что в кино ему делать нечего, вдруг начали поступать новые предложения. Его еле уговорили сняться в фильмах «Приходите завтра» Е. Ташкова, «Порожний рейс» М. Венгерова, «Родная кровь» М. Ершова (все в 1962 г.).

Знаменательной стала для творческой жизни А. Папанова встреча с К. Симоновым. Вместе с режиссером А. Столпером тот работал над картиной «Живые и мертвые» (1963 г.) и выбрал на роль генерала Серпилина именно Папанова, после того как увидел его в спектакле «Дамоклов меч». Он не только настоял на его кандидатуре, но и заставил самого артиста поверить в успех. С первых же кадров, по мнению Симонова, исполнитель попал в самую сердцевину образа, своим человеческим и актерским обаянием покорил и авторов, и партнеров по съемкам. Понравился он и зрителям – фильм занял первое место во всесоюзном кинопрокате, а затем получил призы на кинофестивалях в Москве, Карловых Варах и Акапулько. В 1966 г. как исполнитель роли Серпилина Папанов был удостоен Государственной премии РСФСР им. братьев Васильевых.

Этот долгожданный успех пришел к актеру в возрасте сорока с лишним лет, наконец-то он почувствовал сладость работы в кино и нашел в нем свое место. Отныне Папанов стал сверхпопулярным и среди режиссеров: только за один 1964 г. его пригласили сразу в 10 картин! Конечно, сниматься во всех фильмах было физически невозможно, и он остановился на двух проектах киностудии «Мосфильм» – «Наш дом» В. Пронина и «Дети Дон Кихота» Е. Карелова. Дальше – больше. Судьба как будто исправляла свои ошибки, давая теперь возможность наверстать упущенное. Папанов снимался почти без отдыха, в нескольких картинах одновременно, упивался разнообразием ролей. В 60-е годы вышло тридцать картин с его участием, в 70-е годы к ним прибавились еще двадцать. Наиболее популярными стали герои Папанова в фильмах «Берегись автомобиля» (роль тестя), «В городе С.» (Ионыч), «Золотой теленок» (Лоханкин), «Служили два товарища» (командир полка), «Бриллиантовая рука» (Лелик), «Белорусский вокзал» (Дубинский), «Адъютант Его Превосходительства» (атаман), «Джентльмены удачи» (сосед по гостиничному номеру), «Двенадцать стульев» (Воробьянинов) и многие другие.

О неограниченных творческих возможностях А. Папанова свидетельствовали и театральные работы: «Двенадцать стульев», «Яблоко раздора», «Доходное место» и др. Много сил было отдано образу Василия Теркина в спектакле «Теркин на том свете», но, к великому огорчению всей труппы, цензура его сняла.

Вообще у Папанова хватало огорчений и не только в творчестве. По-разному складывались отношения в театре, не все его любили, а со временем и откровенно завидовали. Показателен случай, когда он оказал сопротивление милиционеру, дело раздули, на собрании коллектива встал вопрос о лишении его звания заслуженного артиста, и некоторые рьяные поборники нравственности проголосовали за это. Не раз он порывался уйти в другой театр, например во МХАТ, но заложенное в его характере постоянство, элементарная порядочность брали верх. Он не мог «выйти из обоймы», как сам выражался, подвести товарищей, сорвать спектакли. Актер очень дорожил полученными ролями Городничего в «Ревизоре», шафера в «Клопе», Фамусова в «Горе от ума», Хлудова в «Беге».