Валерий Барынин родился 25 марта 1940 года в городе Арзамасе.
Его отец Николай Александрович Барынин был военным, старшим лейтенантом, погибшим в 1942 году.
После начала войны его мать Серафима Леоньтевна Щепочкина увезла сына в свой родной город Киров к своей матери Наталии Сергеевне, где Валерий и вырос, и всегда считал Киров своим родным городом.
Наталия Сергеевна (иногда пишется Наталья) была замужем за Леонтием Щепочкиным, купцом первой гильдии. Валерий Николаевич так написал на обложке своего диска «Эх, цыгане!» об этом браке: «Дед мой, купец первой гильдии, страстно любил цыган. Он «выкрал» мою бабушку, когда ей было 13 лет. В 14 она родила первого из 11 детей.»

Военное детство было тяжелым. Жили сначала в бараке с земляным полом с туалетом на улице. Ходили с бабушкой христорадничали, стучали в окошко и пели «Отче наш, Богородица, радуйся» и собирали подаяние.
Потом, когда он учился в классе четвертом-пятом, семья переселилась в деревянный двухэтажный дом в крохотную комнату-пенал.
Валерий всегда тянулся к музыке. Уже в школе просил маму купить ему какой-нибудь музыкальный инструмент: баян, гармошку или гитару, но та отвечала: "Сынок, ты видишь, вот у меня есть два платья. Одно изумрудно-зеленое на выход, и второе вот повседневное. Которое продать?"
Будущий певец неоднократно в интервью говорил, что от природы ему было дано всего полторы октавы и слух был не очень, но потом слух развился почти до абсолютного, а диапазон голоса достиг четырех октав. Голос с детства был громкий "как дизель", но неуправляемый, потому что никакого представления о нотах и тональностях у мальчика не было. И когда родственники на праздники за столом садились и тихонько пели хором задушевные песни а Валерий начинал им подпевать, то он их заглушал и больше никто никого не слышал. Тогда его одёргивали, говорили: "не умеешь петь — не ори, сиди и молчи, слушай". В результате лет с двенадцати он выходил на высокий берег Вятки, в поля или в леса и там "отводил душу".
В четырнадцать лет был исключён из 14 школы города Кирова за отказ учить "язык фашистов, убивших отца".

Валерий Барынин продолжил учебу в вечерней школе, так как пошел работать на Кировский оборонный завод (ныне "Авитек").
Был механиком, сборщиком, слесарем, токарем по металлу, обкатчиком, киномехаником.
Параллельно, как и все мальчишки, увлекался спортом, играл в заводских командах в футбол и хоккей (был вратарем), занимался боксом и борьбой.
А когда Барынину было семнадцать лет, в дело вешался случай…
Рабочие на заводе делали крепкий напиток из клея БФ, который разливался в 200-литровые бочки. Брали ведро с клеем, водой и солью, на сверлильный станок наматывали проволоку и заводили станок. Клейкая часть наматывалась, а остаток «прогоняли» через мякиш хлеба и получали чистейший спирт. Пили и разбавленный, и неразбавленный (это называлось «пойти поприветствовать Бориса Федоровича» - и как расшифровка БФ и по имени первого секретаря). Однажды они «Бориса Федоровича» шарахнули, снежком заели и пошли расчищать заводской стадион. И так как после такой выпивки без песен не обойдешься, закричали во всю глотку «Эй, ухнем!», и Барынин громче всех. Вдруг какой-то человек из окна по пояс высунулся и спрашивает, кто пел. Никто не признался. Тогда он на улицу выскочил ... Это был руководитель Вятского хора потребкооперации Борис Александрович Молдавский. Коллеги Барынина «сдали», и Молдавский предложил Валерию петь в его хоре. Барынин ни в какой хор сначала не захотел идти. Но потом Молдавский не поленился, цеха прошел, нашел паренька и убедил его все же начать заниматься пением серьезно.
В результате, в том же 1957 году Валерий Барынин стал лауреатом городского смотра народной песни, заняв на нем первое место. Наградой за победу в конкурсе стала рубаха-гавайка лимонно-желтого цвета, с зелеными пальмами и красным попугаем какаду. Ценность награды иллюстрирует тот факт, что все ребята, друзья Барынина одалживали у него эту рубашку, когда ходили на свидания – она срабатывала безотказно.
Потом юношу потянуло на романтику, и он записался в геологоразведочную партию. Был сначала чернорабочим, потом окончил курсы геологов-геофизиков. В геологоразведке в поисках урана, тория, магния прошел весь Красноярский край, с юга до Таймыра. В свободное время, вечером у костра, геологи пели под гитару. Пел и Валерий Барынин, и коллеги говорили ему: "Парень, да по тебе консерватория плачет".
Приехав в отпуск, Барынин опять попадает в народный хор, на сей раз – Сибирский. Причем попадает случайно – за компанию. Его приятель Вячеслав Юсупов, обладатель красивого тенора, предложил ему пойти туда «попробоваться», так как был объявлен набор в хор. В результате прослушивания взяли обоих. Сначала Валерий был просто хористом, потом стал солистом. Благодаря известному американскому импресарио Солу Юроку вместе с Сибирским хором в двадцать лет Барынин впервые попал на гастроли за рубеж. Потом перешел на работу в Омский хор.
В газете Труд от 1 апреля 2000 г. в статье «Валерий Барынин: устал я греться у чужого огня» рассказывают о том, как упорно работал Валерий Барынин над преодолением своего вятского говора:
«Однажды Валерий присел в скверике перед драматическим театром. Сидевший рядом старичок, похожий на "всесоюзного старосту" Калинина, но оказавшийся актером, заговорил с юным соседом, стал расспрашивать... Приговор вынес неутешительный: "Нет, молодой человек, вы никогда не станете артистом, потому что у вас вялые губы и совершенно не наработан амбушюр". Ошарашенный, парень бродил, размышляя: "Как он сказал? Ам-ба-шур? Что это за штуковина?". Выяснилось, что под загадочным словом "амбушюр" скрываются натренированность, выносливость, сила, гибкость и подвижность губных и лицевых мышц. А губы у Валерия вялые были потому, что говорил-то он по-вятски: "Чо вы тута-ка расселися-то? Айда-ко-те будем чяевничать ли, чо ли". Представляете, с таким говорком Онегин или Мистер Икс обратились бы к своим возлюбленным? Но, как говорится, вятский народ - хватский. Раздобыл себе Валерий магнитофон, слушал лучших дикторов по радио, а потом, копируя их произношение, читал газеты, записывал на магнитофон, снова слушал...»

Работая в Омском народном хоре, Валерий Барынин неожиданно получил приглашение от молодого дирижера Омского театра музыкальной комедии Бориса Вениаминовича Чебоксарова. Он сказал молодому солисту: «слушай, чего ты там в этом хоре стоишь, как белая ворона (Валерий был на голову выше всех ростом и выделялся своей черной шевелюрой), давай, приходи к нам.»
Первой ролью на сцене был Черный Боря. Это был крохотный эпизод в спектакле «Друзья Милены». Там было всего две фразы: «Простите, вы из какого института?» — «Из Политехнического». — «А наши тут не проходили?» При первом выходе на сцену случилось неожиданное: внезапно главный герой, которого играл актер Николай Масюков, сам спросил у героя Барынина: «Простите, вы из какого института?». Но тот каким-то чудом нашелся и ответил: «Я-то из политехнического, а вы из какого?» И герой сел в лужу, потому что это была его фраза... За кулисами и в яме раздался сдавленный, но ясно слышный хохот. Экзамен на профпригодность был сдан успешно.
Валерий Барынин проработал в Омской музкомедии полтора года и за это время сыграл несколько главных ролей:

• Армана в оперетте Ф.Легара «Фраскита»;
• Алешу Нечаева в оперетте А.Петрова «Жили три студента»;
• Андрея Бакланова в оперетте Ю.Милютина «Цирк зажигает огни»;
• И две совершенно противоположных роли: Джима Кеньена и Чёрного орла в оперетте Р.Фримля «Роз Мари».

И все это - не зная элементарной нотной грамоты.
Молодой человек понимал, что для дальнейшего развития своего таланта, поиска своего места в искусстве необходимо подкрепить природное дарование техникой. Как процитировано в упомянутой выше газете «Труд»: «Мучила мысль, что почти все делаю вслепую, интуитивно.»
Валерий Барынин оставляет театр, хорошую зарплату и едет в Свердловск, чтобы начать все сначала и поступить на первый курс Уральской консерватории им.М.П.Мусоргского.