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

Так вот мы решили спасать Ларисину картину через Машерова, кандидата в члены Политбюро. Происходило все в белорусском Госкино. Пришел Машеров, с ним вся его свита, смотрящая не столько на экран, сколько на то, как хозяин будет реагировать, я тоже смотрел больше на него, чем на экран, но по другой причине, как вы понимаете. Он пришел казенно-бодрый, не очень представляя, что увидит. Думаю, он уже знал, что в Москве Гришин относится к картине резко отрицательно, и вступать с ним в конфликт ему вряд ли хотелось. Посмотрим, увидим, скажем. Но вот в какой-то момент вижу: потекли у него слезы. Тогда я понял, что все в порядке, потому что это был, наверное, единственный член Политбюро (или там кандидат), который мог еще плакать. Когда вспыхнул в зале свет, зареванный Машеров бросился целовать Ларису: как же вы, такая молоденькая, как же вы могли?.. Так точно все прочувствовали, увидели, показали партизан...»

Несмотря на то, что столичные чиновники делали все, чтобы «Восхождение» посмотрело как можно меньше людей, фильм собрал около 11 миллионов зрителей. В 1977 году он был удостоен призов на фестивалях в Риге и Западном Берлине.

Между тем после успеха в «Восхождении» за Гостюхиным стали охотиться и другие режиссеры. Так как в театре ему отказались предоставить академический отпуск для съемок, актер из него ушел. И один за другим выходят фильмы с его участием: «Предварительное расследование» (1978), «Случайные пассажиры», телефильм «Время выбрало нас» (оба - 1979), «Живой срез», «Старшина», «Охота на лис» (все - 1980), «Возьму твою боль» (1981).

В 1980 - 1982 годах на Гостюхина посыпались всевозможные награды. Он получил: премию Ленинского комсомола (за телефильм «Время выбрало нас»), серебряную медаль имени А. Довженко (за фильм «Старшина»), Государственную премию Белорусской ССР (за фильм «Возьму твою боль»), приз за лучшую мужскую роль на XXV Международном кинофестивале авторского кино в Сан-Ремо (за фильм «Охота на лис»).

В 1982 году В. Гостюхину присвоили звание заслуженного артиста РСФСР.

В начале 80-х Гостюхин перебрался на постоянное место жительства в Минск. Причины этого переезда были как творческого, так и личного порядка. Во время съемок на «Беларусьфильме» в картине «Волки» по В. Шукшину актер влюбился в художника-гримера и ради нее покинул Москву. Столичную квартиру он оставил первой жене и дочери (родилась в 1972 году). В 1982 году во втором браке у Гостюхина родилась еще одна дочь.

Между тем спрос на Гостюхина-актера в российском кинематографе держался вплоть до начала 90-х годов. За это время он снялся еще в целом ряде заметных картин, получил множество различных наград. На его счету были фильмы: «Магистраль», «Такая жесткая игра - хоккей», «Лунная радуга», «Берег» (все - 1983), «Контракт века», телефильм «В поисках капитана Гранта» (оба - 1985), «Зина-Зинуля», «Знак беды» (1986), «Без солнца», «Моонзунд» (1987), «Наш бронепоезд», «Большая игра» (1988), «Смиренное кладбище», «Похищение чародея» (1989), «Автостоп», «Все впереди» (1990).

За художественный фильм «Берег» Гостюхин был удостоен Государственной премии СССР 1985 года; в 1989 году в Твери он получил приз зрительского жюри за роль в фильме «Наш бронепоезд», а также специальный приз Гильдии киноактеров «За вклад в развитие советского кинематографа»; за лучшую мужскую роль в ленте «Смиренное кладбище» Гостюхин получил два равных приза (за лучшую роль и приз зрительских симпатий) на II Всесоюзном фестивале актеров «Созвездие-90».

В 1991 году на экраны вышел фильм Никиты Михалкова «Урга», в котором Гостюхин сыграл одну из главных ролей - шофера Сергея. На Международном кинофестивале в Венеции в том же году фильм стал настоящей сенсацией: его создателям был вручен главный приз - «Золотой лев» и приз экуменического жюри за гуманное отображение проблем семьи. Кроме этого фильм собрал еще кучу всевозможных призов: «Кинотавр-92» «Ника-92», «Феликс-92», «Кельн-92».

В начале 90-х Гостюхин получил приглашение от Сергея Бондарчука сыграть роль брата Григория Мелехова в российско-итальянской версии «Тихого Дона». На этих съемках с актером едва не случилась беда. Рассказывает А. Сыров: «Снимаем сцену расстрела брата Григория, которого играет Гостюхин. Дело происходит зимой, на натуре. Вьюга. Гостюхин стоит на краю обрыва, босой, в одной рубашке. Итальянский пиротехник обвил его «посадками» в местах, куда как бы попадут пули, подсоединил проводочки. Сидят, ждут. А «посадки» - это такие маленькие резиновые пакетики, в которые наливают жидкость, имитирующую кровь. Затем выводят наружу два провода, подключают к генератору, в нужный момент замыкают, и происходит такой мини-взрыв - «кровь» выступает из раны. Так вот, сцена готова. Начинаем работать, «посадки» не взрываются. Второй дубль, то же самое. Народ начинает нервничать, пиротехник подбегает к Гостюхину, что-то мудрит с проводочками, наконец машет рукой - мол, все нормально. Снимаем третий дубль. И тут как рванет. И сразу страшный гостюхинский крик. Подбегаем, смотрим, а у него вся грудь - один настоящий кровавый синяк. Бондарчук чуть морду не набил итальянцу, еле успокоили. Потом выяснилось, что бедняга так перепугался от своих неудач, что дал заряд раз в семь больше, чем требовалось».

В 1992 году на экраны вышли два фильма, в которых Гостюхин сыграл две большие роли: в «Генерале» он предстал в образе легендарного генерала А. В. Горбатова, а в боевике «Америкэн бой» сыграл сыщика Мухина.

В 1993 году имя Гостюхина прогремело в скандальной хронике - он публично оскорбил Булата Окуджаву. Сам актер вспоминает об этом так: «После событий 93-го года, когда я даже в кошмарном сне не мог представить, что в центре Москвы танки откроют огонь и людей будут убивать просто так, Окуджава при ехал на гастроли в Минск, и выставили большой пикет около филармонии, где он выступал. А я читал интервью, где он говорил, что наслаждался произошедшим, как детективом. Не знаю, почему он так сказал. Окуджава - моя молодость, я все его песни знаю наизусть, нежный человек. И вдруг такая радость по поводу убиения людей! Для меня это было настолько сильным потрясением, что я просто разорвал конверт и разбил его пластинку перед концертом. Был большой шум. В Верховном Совете в Минске этому было посвящено заседание. Призывали меня посадить. Это был кошмар!..