Фамилия Веденев (и её вариант Веденёв) образована от крестильного имени Венедикт, которое пришло на Русь вместе с христианством. Латинское Benedictus переводится как «благословенный», а по другой версии — «тот, о ком хорошо говорят». В русской народной среде имя Венедикт быстро обросло обиходными формами, и одной из них стало Веденя. Именно эта сокращённая, «домашняя» версия и легла в основу фамилии: типичный для русской ономастики суффикс -ев присоединялся к основам, оканчивающимся на мягкий согласный, что и дало форму Веденев (а не Веденов).

Первые письменные свидетельства о фамилии относятся к концу XVI века. В исторических документах за 1590 год упоминаются помещики Веденевы, жившие на территории Мещеры и Касимова. Это один из ранних примеров, когда фамилия уже закрепилась за служилым сословием — значит, к тому времени она прошла стадию отчества и стала наследственной. Сама форма Веденя — не единственная производная от Венедикта: в народе бытовали также Ведих, Ведюня, Ведяй, но именно вариант с суффиксом -еня дал начало этой фамильной линии.

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