Потерпев неудачу на кинематографическом фронте, Папанов познал победу на театральной сцене. В конце 50-х в репертуар Театра сатиры был принят «Дамоклов меч» Назыма Хикмета. Папанову в нем досталась центральная роль – Боксера. Когда труппа театра узнала об этом назначении на роль, то многие откровенно удивились. Им казалось, что у Папанова без грима, наклеенных усов или накладных ушей и шеи живой человек на сцене не родится. В своих способностях сыграть эту роль стал сомневаться и сам Папанов. Однако режиссер настоял на своем, и спектакль с участием нашего героя состоялся. Отмечу, что в момент работы над этой ролью Папанов брал уроки бокса у чемпиона Европы по боксу Юрия Егорова.
«Дамоклов меч» имел огромный успех у зрителей и круто изменил творческую судьбу нашего героя. После него на Папанова всерьез обратили внимание кинематографисты. Например, тот же Эльдар Рязанов. В 1960 году он задумал снимать фильм «Человек ниоткуда» и на роль Крохалева пригласил Папанова. При этом режиссеру пришлось приложить много сил, чтобы уговорить актера сниматься. К тому времени Папанов полностью уверился в том, что он не «киногеничен», и сниматься наотрез отказывался. Чтобы убедить его в обратном, Рязанову пришлось буквально валяться у него в ногах и чуть ли не за шиворот втягивать его в кинематограф. В конце концов сопротивление Папанова было сломлено.
Партнером нашего героя по фильму был другой замечательный актер – Юрий Яковлев. Последний о тех съемках вспоминает: «На первых пробах я увидел человека, который стеснялся, боялся, переживал неуверенность в том, что способен осилить сложнейшую актерскую трансформацию в кино, и я подумал, как мне будет трудно с таким партнером. Давно, со студенческой скамьи, я усвоил, что не всякий хороший актер становится хорошим партнером, а партнерство для меня – основа творческого бытия на сцене и на съемочной площадке. После второй и третьей проб мне стало казаться, что партнерский альянс с Папановым может состояться.
Обретя себя в ролях вождя племени Тапи, Профессора и других, столь же противоположных по характерам, Толя раскрепощался в личном общении со мной и другими партнерами, стал веселым и добрым, много и сочно шутил. Я любовался его ребяческими проявлениями, которые его как личность очень украшали. Я был рад, что мои опасения остались далеко позади, и наше творческое партнерство на многие годы переросло во взаимные дружеские симпатии. Позже, встречаясь в концертах, мы неизменно радовались друг другу».
Фильм «Человек ниоткуда» в то время так и не вышел на широкий экран. Картина была наспех показана в домах творческой интеллигенции, не более двух-трех дней продержалась на премьерном экране. Ее судьбу решил тогдашний главный партийный идеолог Михаил Суслов. Однажды он возвращался в Кремль по Калининскому проспекту и увидел огромную афишу фильма на фасаде кинотеатра «Художественный». Плакат ему очень не понравился, и он коротко бросил: «Снять!» В результате ретивые чиновники сняли не только плакат, но и картину с проката. Ее премьера состоялась только через 28 лет после этого, когда Папанова уже не было в живых.
Это был не последний совместный фильм в творческой карьере Рязанова и Папанова. Буквально в том же, 1961 году вышла их новая работа – десятиминутная короткометражка по рассказу И. Ильфа и Е. Петрова «Как создавался Робинзон», в котором наш герой играл Редактора – душителя прекрасных порывов.
В 1961 году Папанов также снялся в фильме режиссеров А. Митты и А. Салтыкова «Бей, барабан» в роли поэта Безлошадных и в картине Татьяны Лукашевич «Ход конем» – в роли Фонарева. Однако обе эти роли не принесли актеру творческого удовлетворения.
В 1962 году на Папанова обратили внимание три режиссера – Евгений Ташков, работавший тогда на Одесской киностудии, Владимир Венгеров и Михаил Ершов (оба – с «Ленфильма»). Первый предложил нашему герою исполнить положительную роль скульптора в своем фильме «Приходите завтра» (в нем Папанова озвучивал другой актер, так как голос Папанова считался некиногеничным), второй в картине «Порожний рейс» – отрицательную роль директора леспромхоза и третий – в фильме «Родная кровь» эпизодическую роль подлеца – мужа главной героини картины (ее играла Вия Артмане). Все три фильма вышли в прокат в 1963–1964 годах и имели разный успех у зрителей: «Приходите завтра» собрал 15,4 млн. зрителей, «Порожний рейс» – 23 млн. и приз на Московском кинофестивале, «Родная кровь» – 34,94 млн. Критика отметила прекрасную игру Папанова во всех этих картинах, однако попасть в первую шеренгу тогдашних советских кинозвезд актеру так и не удалось. Зрители его знали, но о всенародной любви тогда говорить было еще рано.
Настоящий успех пришел к Папанову год спустя – в 1964 году. Произошло это при следующих обстоятельствах. В начале 60-х годов на спектакле Театра сатиры «Дамоклов меч» побывал писатель Константин Симонов. Игра Папанова в нем настолько поразила его, что он предложил кинорежиссеру А. Столперу, который в 1963 году решил экранизировать его роман «Живые и мертвые», взять этого актера на роль генерала Федора Серпилина. Поначалу Столпер сомневался, так как знал Папанова как исполнителя в основном отрицательных, комедийных ролей (тот же Боксер был ролью резко отрицательной). Здесь же предстояло сыграть роль положительную, даже героическую. Однако Симонов настаивал на своем выборе, и режиссер в конце концов согласился.
Долго сомневался в своих способностях сыграть положительного героя и сам Папанов. Как вспоминает Н. Каратаева: «У нас в общежитии был длинный коридор, и в нем стоял общий телефон. Ему несколько раз звонили, уговаривали, а мы все стояли и слушали, как он отказывался играть Серпилина: „Ну какой я генерал? Да нет, ну что вы, я не могу…“ И уже после выхода картины он мне часто говорил: „Что это все восторгаются? Чего там особенного я сыграл?“
Действительно, после выхода этого фильма на широкий экран к Папанову пришла всесоюзная слава. Роль генерала Серпилина опрокинула довольно прочно устоявшееся мнение о нем как об актере комедийно-сатирического направления с некоторыми драматическими задатками. В прокате 1964 года «Живые и мертвые» заняли 1-е место, собрав на своих просмотрах 41,5 млн. зрителей. В том же году картина получила призы на фестивалях в Москве, Карловых Варах и Акапулько. В 1966 году фильм был удостоен Государственной премии РСФСР.
Как вспоминает исполнитель главной роли в этом фильме К. Лавров: «Столпер с огромным уважением относился к Папанову. С самого начала чувствовалось, что этот актер – лидер в картине. О Симонове и говорить нечего: Константин Михайлович не однажды рассказывал мне, как ему нравится Толя и точным попаданием в самую сердцевину образа Серпилина, и в других ролях, и просто по-человечески. Забегая вперед, скажу, что к Папанову устремлялись душой сразу, без обычной в человеческих отношениях разведки и приглядывания. Так, в Звездном городке, куда мы привезли только что смонтированный фильм „Живые и мертвые“ в сопровождении Столпера, Папанова и моем, Юрий Гагарин улучил минуту, чтобы остаться наедине с Толей и со мной, увел нас в какую-то из дальних комнат клуба космонавтов, и мы незабываемо пообщались за бутылкой кубинского рома».
