Фёдор Раззаков «Кумиры всех поколений»
Демобилизовавшись, Гостюхин вернулся в Москву (жил в Долгопрудном) и стал методично обходить все столичные театры в поисках работы. Однако его никуда не брали. И только в Центральном академическом театре Советской Армии ему предоставили шанс: пока в труппе нет свободной актерской вакансии, поработать мебельщиком-реквизитором. Гостюхин согласился. А потом ему улыбнулась удача. Внезапно заболел актер, исполнявший роль старшины Бокарева в спектакле «Неизвестный солдат» по А. Рыбакову, и заменить его предложили Гостюхину. Несмотря на то, что перед премьерой им было сыграно всего две Репетиции, роль Гостюхину удалась. Именно на этом спектакле его и разглядела помощник режиссера Василия Ордынского и пригласила на роль Алексея Красильникова в 13-серийную эпопею «Хождение по мукам».
Между тем параллельно со съемками у Ордынского Гостюхину выпало счастье встретиться еще с одним режиссером - Ларисой Шепитько. Она тогда приступала к съемкам фильма «Восхождение» по повести В. Быкова «Сотников» и искала исполнителя на главную роль - предателя Рыбака. Встретив Гостюхина, с ходу предложила эту роль ему.
Гостюхин вспоминает: «Мне тяжело досталась известность Я шесть лет проработал мебельщиком! Но на картине Ларисы Шепитько я поставил задачу - или умру, или состоюсь! Абсолютно серьезно. Я работал на пределе, и мне это удалось…»
Действительно, после премьеры «Восхождения» Гостюхин «проснулся знаменитым». Однако это пробуждение тогда едва не состоялось из-за того, что у фильма нашлись влиятельные недруги. Но спас ситуацию первый секретарь ЦК КП Белоруссии П. М. Машеров. Рассказывает А. Адамович: «Кто такой Машеров? Отца его в 37-м расстреляли, мать немцы в войну повесили сам он был смелым партизаном, он не зря получил Героя. Был способен на глубокие переживания. «Восхождение» в гришинской Москве явно было обречено (В. Гришин - кандидат в члены Политбюро, первый секретарь МГК КПСС. - Ф. Р.). Решили действовать через Минск. Машеров всегда считал, что надо о партизанах сделать наконец хорошую картину…