Фамилия Валуй — одно из тех прозвищных именований, которые напрямую указывали на род занятий человека. В старину валуем (или волуем) называли пастуха, который пас волов и коров. Скорее всего, именно это «профессиональное» значение и легло в основу фамилии: предок нынешних Валуев был пастухом, и это занятие закрепилось за ним в виде прозвища. Однако прозвище могло появиться и по другой причине. В некоторых русских говорах валуем дразнили медлительного, вялого человека или лентяя — такое значение тоже вполне могло стать источником фамилии. А вот современная ассоциация с несъедобным грибом из рода сыроежек — версия маловероятная, поскольку в древности это слово в таком значении если и употреблялось, то было не настолько распространено, чтобы стать массовым прозвищем.

Прозвище Валуй и фамилии от него — не новодел, а явление древнее. В документах XV–XVI веков встречаются конкретные люди с таким именованием. Например, в 1490 году в Новгороде записан крестьянин Валуйко. Ещё раньше, в 1380 году, на Куликовом поле погиб воевода великого князя Дмитрия Донского Тимофей Васильевич Валуй — ему принадлежало подмосковное село Валуево-Покровское на реке Ликове. Позднее, в 1586 году, упоминается Валуй Григорьевич Киндяков. Эти записи из работ историка С. Веселовского показывают, что прозвище бытовало в разных слоях общества — от крестьян до воевод, и уже в XV веке давало начало фамилиям.

Сама фамилия стоит в ряду так называемых «профессиональных» прозвищ, которые не требуют специального суффикса: она застыла в форме именительного падежа. Такие фамилии нередки в русской ономастике — вспомните хотя бы Соловей, Кузнец или Кожемяка. Фамилия Валуй — это прямое, без изменений, закрепление прозвища, что делает её особенно прозрачной для этимологии.