К сожалению, фильм «Человек ниоткуда» в то время так и не вышел на широкий экран. Картина была наспех показана в домах творческой интеллигенции, не более двух-трех дней продержалась на премьерном экране. Ее судьбу решил тогдашний главный партийный идеолог М. Суслов. Однажды он возвращался в Кремль по Калининскому проспекту и увидел огромную афишу фильма на фасаде кинотеатра «Художественный». Плакат ему очень не понравился, и он коротко бросил: «Снять!» В результате ретивые чиновники сняли не только плакат, но и картину с проката. Ее премьера состоялась только через 28 лет после этого, когда Папанова уже не было в живых.

Между тем это был не последний совместный фильм в творческой карьере Рязанова и Папанова. Буквально в том же, 1961 году, вышла их новая работа — десятиминутная короткометражка по рассказу И. Ильфа и Е. Петрова «Как создавался Робинзон», в котором наш герой играл Редактора — душителя прекрасных порывов.

В 1961 году Папанов также снялся в фильме режиссеров А. Митты и А. Салтыкова «Бей, барабан» в роли поэта Безлошадных и в картине Татьяны Лукашевич «Ход конем» — в роли Фонарева. Однако обе эти роли не принесли актеру творческого удовлетворения.

В 1962 году на Папанова обратили внимание три режиссера — Евгений Ташков, работавший тогда на Одесской киностудии, Владимир Венгеров и Михаил Ершов (оба — с «Ленфильма»). Первый предложил нашему герою исполнить положительную роль скульптора в своем фильме «Приходите завтра» (в нем нашего героя озвучивал другой актер, так как голос Папанова считался некиногеничным), второй в картине «Порожний рейс» — отрицательную роль директора леспромхоза и третий — в фильме «Родная кровь» эпизодическую роль бывшего мужа главной героини картины (ее играла Вия Артмане). Все три фильма вышли в прокат в 1963–1964 годах и имели разный успех у зрителей: «Приходите завтра» собрал 15,4 млн. зрителей, «Порожний рейс» — 23 млн. и приз на Московском кинофестивале, «Родная кровь» — 34,94 млн. (занял 4-е место). Критика отметила прекрасную игру Папанова во всех этих картинах, однако попасть в первую шеренгу тогдашних советских кинозвезд актеру так и не удалось. Зрители его знали, но о всенародной любви тогда говорить было еще рано.

Настоящий успех пришел к нашему герою годом спустя — в 1964 году. Произошло это при следующих обстоятельствах. В начале 60-х годов на спектакле Театра сатиры «Дамоклов меч» побывал писатель Константин Симонов. Игра Папанова в нем настолько поразила его, что он предложил кинорежиссеру А. Столперу, который в 1963 году решил экранизировать его роман «Живые и мертвые», взять этого актера на роль генерала Федора Серпилина. Поначалу Столпер сомневался, так как знал Папанова как исполнителя в основном отрицательных, комедийных ролей (тот же Боксер был ролью резко отрицательной). Здесь же предстояло сыграть роль положительную, даже героическую. Однако К. Симонов настаивал на своем выборе, и режиссер в конце концов согласился.

Между тем долго сомневался в своих способностях сыграть положительного героя и сам Папанов. Как вспоминает Н. Каратаева: «У нас в общежитии был длинный коридор, и в нем стоял общий телефон. Ему несколько раз звонили, уговаривали, а мы все стояли и слушали, как он отказывался играть Серпилина: «Ну какой я генерал? Да нет, ну что вы, я не могу… И уже после выхода картины он мне часто говорил: «Что это все восторгаются? Чего там особенного я сыграл?»

Действительно, после выхода этого фильма на широкий экран к Папанову пришла всесоюзная слава. Роль генерала Серпилина опрокинула довольно прочно устоявшееся мнение о Папанове как об актере комедийно-сатирического направления с некоторыми драматическими задатками.