Гостюхин был народным еще задолго до того, как ему присвоили это звание. Большинство его героев - настоящие мужчины. Среди фильмов с его участием такие яркие ленты, как "Председатель", "Восхождение", "Берег", "Время выбрало нас", "Возьму твою боль", "Урга. Территория любви", "Дальнобойщики" и многие другие.

Владимир Гостюхин родился 10 марта 1946 года в Свердловске в рабочей семье. "Все мои предки - с запада России, рассказывает актер. - Дед мой - русак - женился на крещеной еврейке из местечковой Белоруссии. Отец мой - из Вятской губернии (в те времена Кировской) - совершенный русак".
С детских лет родители Владимира Василий Павлович и Александра Ивановна приучили сына к труду. Семья Гостюхиных жила очень бедно. Отец - инвалид войны, мама постоянно была с ним, помогала ему…
По окончании школы Владимир поступил в радиотехникум. Днем он учился, а вечерами работал электриком на стадионе. Участие в студенческом спектакле изменило жизнь Владимира. Он настолько увлекся театром, что бросил учебу и стал заниматься в студии при Доме культуры.
В 1965 году Владимир Гостюхин поступил в ГИТИС, после окончания которого в 1970 его призвали в армию. Он служил в разведроте знаменитой Таманской дивизии. "Считаю, что мужчина должен отслужить в армии. Испокон веку на Руси считалось это святым делом" - говорит Владимир Васильевич.

Вернувшись из армии, Владимир Гостюхин поступил в Центральный академический театр Советской Армии, но не актером, как этого следовало бы ожидать, а мебельщиком-реквизитором. А на сцену он впервые вышел, заменяя заболевшего артиста. Первой театральной работой актера стала роль старшины Бокарева в спектакле "Неизвестный солдат" (1974).
Владимир Васильевич вспоминает о том времени: "Я шесть лет двигал мебель на спектаклях и ждал своего часа. "Как ты выдерживаешь, как не сопьёшься?" - сочувствовали мне актёры. А я не обращал внимания на раздоры и работал. В трудовой книжке - одни благодарности. Меня так воспитали мои родители…"

В кино Гостюхин дебютировал еще на последнем курсе ГИТИСА, снявшись в эпизодической роли солдата Вехова фильме Марлена Хуциева "Был месяц май" (1970). А первую заметную роль сыграл в фильме Василия Ордынского "Хождение по мукам" (Красильников). Но для зрителей этот актер начался с ленты Ларисы Шепитько "Восхождение", вышедшей в 1976 году.
Приглашение Ларисой Шепитько на одну из главных ролей мебельщика-реквизитора Театра Советской Армии Владимира Гостюхина было для всех полной неожиданностью. И для самого Гостюхина, разумеется, в первую очередь. Хотя, "прочитав повесть Василя Быкова "Сотников", - вспоминает актер, - я был так потрясен образом Рыбака, что тогда же внутренне решил: это судьба. Я чувствовал, что это мое, что я смогу…".
Роль предателя Рыбака Владимир Гостюхин сыграл сильно и убедительно. Эта работа ярко продемонстрировала драматический талант актера. Владимир Гостюхин стремился передать живое движение характера, меняющегося в зависимости от тех или иных жизненных обстоятельств. Зажатый в рамки установленной режиссером схемы образа, он сумел создать (особенно в первой половине ленты) более глубокий характер, приблизившись к тому пониманию, какое было заложено в повести Василя Быкова.
Владимир Гостюхин делится своим ощущением этой роли: "Для меня он не был предателем изначально. Я видел слабости этого человека и те обстоятельства, выписанные Быковым, которые загнали его в угол. Именно обстоятельства привели его к такому страшному выбору. Не Рыбак виноват, а политики, которые не дают простым людям заниматься своим делом. Ведь Рыбак создан растить хлеб, кормить людей, а он попадает в такие жестокие обстоятельства, для которых не создан".

Можно было ожидать после "Восхождения", что Владимиру Гостюхину придется играть отрицательных, несимпатичных героев. К счастью, этого не произошло. Почти все персонажи его последующих фильмов неординарны. Актер, необыкновенно требовательный к себе, создавал на экране сложные, порой запутанные русские характеры. Пожалуй, только Боборыкин в "Предварительном расследовании" Андрея Разумовского кажется вполне традиционным.
В новелле "Волки" в киноальманахе "В профиль и анфас" и в "Чужой компании" Гостюхин играет героев, которых трудно оценить однозначно. Интересна роль Кацубы в киноповести "Старшине". А в мелодраме "Случайные пассажиры" (роль - шофер Иван Жаплов) и психологической драме "Охота на лис" (роль - Виктор Белов) актер создал характеры, ранее неведомые нашему кино, отказываясь от устаревших представлений о стерильно положительных и так же стерильно красивых героях-современниках.
70-е - 80-е годы вообще были наиболее плодотворными в творчестве актера. Владимир Гостюхин много снимался. Экран не прошел мимо фактуры Гостюхина - "народности" облика, мужицкой основательности. Его облик работал как образ в "Роднике", где Гостюхин играл крестьянина и воина Касьяна, в мелодраме "Белый ворон", где он был работягой-шахтером, в драме "Возьму твою боль", где актер играл крестьянина Ивана Батрака.
Но уже майор Мак-Наббс в телесериале "В поисках капитана Гранта" сыгран с большой долей актерского озорства, стилизаторства. На резкой смене привычного гостюхинского имиджа сыгран и острохарактерный, почти комедийный атаман Платов в "Левше". Столь же неожидан, но и абсолютно узнаваем воинствующий хам Меженин в киноромане "Берег" (Госпремия СССР, 1985).
Трагическая раздвоенность вора Васьки Пепла из фильма "Без солнца" (1987, по пьесе М. Горького "На дне", реж. Ю. Карасик) еще раз проживалась Гостюхиным на современном материале в неразрешимой драме сломленного, но из последних сил бунтующего могильщика Воробья в картине Итыгилова "Смиренное кладбище" (1989). Не менее трагичен бывший командир лагерной охраны Кузнецов из киноповести Михаила Пташука "Наш бронепоезд" (1988), бившийся в бесполезных попытках самооправдания и кончавший самоубийством.
В 1990 Гильдия киноактеров отметила Гостюхина призом "За выдающийся вклад в профессию".