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

Менее вероятная, но упоминаемая в словарях версия связывает прозвище с грибом-валуем. Это несъедобный гриб из рода сыроежек, который в некоторых регионах называли «валуй» или «валуёк». Слово действительно есть, но для прозвища оно подходит хуже: грибная тематика в прозвищах встречается реже, чем профессиональная или характерологическая.

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

С точки зрения словообразования фамилия простая и прозрачная. Суффикс «-ев» указывает на русское, а не украинское или белорусское происхождение. Однокоренных фамилий в русском языке немного, и все они редкие: Валуевский, Валуйкин, Валунов — но именно Валуев остаётся самым известным и исторически обоснованным.