Фамилия Веденеева образована от имени Веденей — одной из народных, обиходных форм крестильного имени Венедикт. Исходное латинское слово benedictus означает «благословенный»; по другой версии — «тот, о ком хорошо говорят». В русской традиции имя Венедикт, как и многие другие календарные имена, давало целый ряд производных форм: Веденей, Веденя, Веденец. От одной из них через притяжательный суффикс -ев и появилась фамилия, отвечающая на вопрос «чей?» — «сын Веденея».

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

Среди известных обладателей фамилии — Борис Евгеньевич Веденеев (1884/85–1946), российский гидроэнергетик, один из руководителей строительства Волховской и Днепровской ГЭС. Его пример показывает, что носители фамилии встречались в разных сословиях — от помещиков XVI века до инженеров XX века. Потомок человека по имени Веденей со временем и получил фамилию Веденеева.