Приемыхов умер от рака мозга. Болезнь проявилась внезапно, видимо, как следствие огромного перенапряжения, которое Приемыхов испытал во время работы над своим последним фильмом – «Кто, если не мы». Вот как описывает это жена режиссера Любовь Приемыхова:

«Работа была сложная – изменились времена, все стало измеряться деньгами, отношения в группе складывались непростые. Мне хотелось быть рядом с ним, как-то помочь, но на картину Валера меня не взял: у него сохранились несовременные представления о порядочности. Он считал некорректным протежировать своей жене, а также, попросив руководство о подобном «одолжении», боялся потерять независимость.

Съемки иногда продолжались двенадцать часов, все на нервах, как всегда у него. Валера был недоволен администрацией, столкновения происходили буквально по мелочам. Я думаю, но, видимо, так оно и есть, именно тогда и подступила болезнь – из-за морального и физического истощения, нервных перегрузок. У него начались мучительные головные боли. Я просила его сходить к врачу, но времени не было, шли съемки…

После завершения работы над фильмом головные боли у него усилились, я видела, что он уже горстями принимает обезболивающие таблетки. И в конце концов он не выдержал и пошел к врачу. Диагноз оказался страшным. Еще год он боролся с болезнью. Но надежда была, у меня по крайней мере. И я ему внушала эту надежду…»

Рассказывает Е. Васильева: «У Валеры обнаружили болезнь. Я не знаю, что было бы с ним, если бы не Церковь. Диагноз был понятен сразу. Я уверена – эту болезнь можно победить при помощи Господней, и много тому примеров. У него был шанс. Я ему сказала: «Ситуация крайняя. Ты должен поменять всю свою жизнь, абсолютно всю».

Он: «А что бы ты сделала на моем месте?» – «Я бы на твоем месте ушла в монастырь».

Он: «Добрая ты, волчица…» Все хотел перевести в шутку.

А я говорила серьезно: «Ты так не излечишься. Сейчас пойдут полумеры – химия, облучение…» Так и получилось…»

В июне 2000 года Приемыхов угодил в больницу после того, как у него внезапно поднялась температура до 37 с небольшим градусов и не опускалась в течение нескольких дней. Полагая, что все обойдется, Приемыхов взял с собой свой новый сценарий – о князе Владимире Красное Солнышко. Однако в конце августа больному стало совсем плохо.

Рассказывает дочь режиссера Нина Приемыхова: «Когда папа заболел, не хотел говорить, насколько это серьезно, а я делала вид, что не знаю. Не хотел, чтобы я видела, как его на каталке возили или укол ему делали. Если боли начинались, всегда говорил: «Выйди!» Или я его прошу: «Пап, давай я тебя покормлю». – «Нет». И только когда я уходила, ел. Не мог показаться слабым, беспомощным. Если бы мне сразу всю правду сказали, я бы только им одним занималась, у меня важнее дела не было бы…»

Рассказывает жена режиссера Любовь Приемыхова: «У нас часто заходил разговор о венчании, наш духовный отец ругал нас за нерешительность. Валера смущался, что в таком возрасте будет в роли жениха. К сожалению, кончилось это трагично… Мы оба верили, он поправится, отложили это дело до выздоровления, и вдруг случился кризис. Я обратилась к батюшке, он согласился обвенчать нас в больнице. Договорились на следующий день… А ночью 25 августа он умер. Я так сокрушалась, а батюшка мне сказал: «Люба, утешьтесь тем, что Бог целует намерения».

Рассказывает Е. Васильева: «Началось бесконечное лечение. Правда, Валера очень верил в силу молитв, исповедовался: часто причащался и читал акафист, который мы все читали перед иконой Всецарицы – она помогает страждущим от раковой болезни.