Los orígenes de este municipio se remontan a la Edad del Bronce y en sus alrededores hubo también una intensa colonización romana como atestiguan los restos de lápidas funerarias encontradas en los parajes de Valdelagrulla, Palacios, Majanos y Majales.
A finales de la Edad Media era un conglomerado de casas en torno al barrio de Gurumeña, probablemente antiguo poblado árabe. A partir de este núcleo fue creciendo el pueblo, construyéndose después la iglesia de Nuestra Señora de Bienvenida.
El lugar de Valdefuentes perteneció a la Orden de Santiago, de la que fue desmembrado, con permiso papal, e incorporado a la Corona.
Felipe II de España lo vendió, por escritura fechada el 11 de julio de 1558, a Álvaro de Sande, por los méritos contraídos en la defensa de la plazas de Gelves y Malta. De esta forma Valdefuentes pasó a ser villa de señor laico.
El I Señor de Valdefuentes mandó construir una casa-palacio, de estilo renacentista, diseñada por Pedro Fernández de Trujillo, y un rollo como signo representativo de su poder jurisdiccional.
Como centros artísticos de esta localidad merecen destacarse:
El Rollo, que preside su plaza, y puede datarse hacia 1565.
El Palacio de los Sande, levantado por Álvaro de Sande, consta de dos plantas, la baja se abre en pórtico arqueado (actualmente macizado) y la superior tiene una galería arquitrabada con gráciles columnas renacentistas (Ver fotos adjuntas).
El Esgrafiado es una técnica de decoración de fachadas de influencia morisca, presente en muchas de sus calles, consistente en extender sobre una fachada dos capas superpuestas de revoco de distinto color, compuesto por una mezcla de cal y arena, en la capa externa se dibuja el motivo ornamental deseado haciéndose desaparecer parte de esa capa externa allí donde sea preciso que aparezca el color de revoco colocado debajo. Mediante este proceso se consigue una decoración bicolor con temas más o menos geométricos repetidos de forma regular por toda la superficie de la fachada.
El Convento de San Agustín. Fundado bajo el patrocinio de Ana de Sande y Padilla y su marido, Alfonso de Lancaster, fue concebido como panteón de la familia, levantándose sobre una lonja elevada, por estas y otras coincidencias se le ha denominado el Pequeño Escorial; el templo conventual es bien proporcionado, con nave central y dos capilla laterales, crucero y ábside de planta rectangular, destacando en su conjunto la carpintería de sus puertas, el retablo mayor y la capilla sepulcral, situada en el trasaltar, siendo su portada obra de transición del herreriano al barroco, también de estilo herreriano es el claustro. En la actualidad se ha convertido en parroquia. La iglesia presenta una nave única de dos tramos, crucero y presbiterio recto, cubriéndose todo ello con una combinación de bóvedas de aristas y de medio cañón, elaboradas con ladrillos. Sobre la zona central del crucero se sitúa una cúpula semiesférica sobre pechinas, sistema que se emplea igualmente para cubrir la sacristía, adosada al extremo oriental del presbiterio. De su exterior cabe destacar la espadaña sobre el lado de la Epístola, con dos arcos rematados en frontón, y la fachada de los pies. Esta última, de cantería, se abre en arco de medio punto entre pilastras acanaladas que sustentan un entablamento de triglifos y metopas. El conjunto se completa con una hornacina central con la imagen del titular y los escudos de los patrocinadores. El templo posee retablo mayor del siglo XVIII con tallas policromadas de la misma centuria. Unido al costado de la Epístola se encuentra el Claustro (recientemente restaurado), con arcos de medio punto en los pórticos del primer piso y en los vanos del superior, y bóvedas de arista en sus galerías.
Iglesia de Nuestra Señora la Virgen de Bienvenida. Destaca por la generosidad de sus proporciones. Edificio barroco de carácter popular construido en el siglo XVII, aunque con diversos vestigios del siglo anterior. Levantado a base de mampostería y sillarejo, consta internamente de una nave con triple tramo y cabecera ochavada de tres paños, a la que se adosa un camarín de planta rectangular. La capilla mayor se remata mediante un casquete de cuarto de esfera, en tanto que la nave aparece cubierta con bóveda de cañón con lunetos, a excepción del tramo inmediato al presbiterio, que presenta crucería sencilla. También bóveda nervada, aunque más compleja, encontramos en la capilla bautismal adosada a los pies, que constituye la base de una maciza torre prismática de tres cuerpos. Posee coro, elevado sobre dos arcos carpaneles, y sencillas portadas, estando la de los pies precedida por un pequeño pórtico.
Contiene esta parroquial diversos retablos e imágenes barrocas de los siglos XVII y XVIII. Merece destacarse el retablo mayor de un cuerpo dividido en tres calles, con la imagen de vestir de la titular.
Las Fiestas en honor a la patrona Nuestra Señora la Virgen de Bienvenida (15 de agosto).
La Feria en honor al patrón San Agustín (28 de agosto). Conocida en la zona es su feria de ganado.
Los Quintos (Fiesta tradicional donde los jóvenes que entran en quintas ese año se divierten con amigos y familia, teniendo la culminación con el baile alrededor de una gran hoguera tras la cena de Nochebuena).
Feria Agroalimentaria, más conocida como Feria del Queso (Un fin de semana de la primera quincena de marzo). Data del año 2000 y se ha convertido en la fiesta de referencia para todos los lugareños y forasteros. Sin duda, el fin de semana en el que Valdefuentes recibe mayor número de visitantes, unos 25.000 desde viernes a domingo, llegando a más de 10 000 el sábado.
Romería de la Magdalena (lunes siguiente al Domingo de Resurrección).
Fiesta de Los Tableros: se celebra el primer fin de semana de octubre en honor a la Virgen del Rosario; de un colorido singular; en síntesis es una ofrenda que se hacía a Diosa Ceres pidiéndole abundancia en las cosechas y en la bonanza del cebo del cerdo para su posterior mat
Otras: Carnavales, Cachetía en los Santos, los Gallos, las Cintas, Festival Vallepop.
Pedro Rubio Liébana (1903-1936): Sacerdote natural de Valdefuentes, estuvo en Montánchez y en Granja de Torrehermosa donde fue fusilado por los republicanos en cumplimiento a su labor hasta el final.Actualmente se en encuentra en situación de estudio para su posible beatificación en el obispado de Coria-Cáceres.
Juan Solano (1905-1986): Escritor e historiador entusiasta de las raíces extremeñas, escribiendo "HISTORIA DEL SEÑORÍO DE VALDEFUENTES". Esta obra rescató el enorme legado que tenemos firmando una estela de defensa del patrimonio de Valdefuentes que será continuada por otros entusiastas valdefuenteños.
José Antonio Pérez Rubio (1945): Doctor y catedrático en Sociología en la Universidad de Extremadura, ExDecano de la Facultad de Empresariales y Turismo de Cáceres. Coautor del libro Mira que te diga e impulsor de la publicación del libro de Juan Solano continuando su legado. Es en la actualidad Cronista oficial de Valdefuentes.
José María Rubio Merino (1966): De padres valdefuenteños, Ingeniero Aeronáutico, Director de Relaciones Iinstitucionales para España de Grupo Eurocopter, coautor del libro Mira que te diga.
José Luis Coca-Pérez (1964) Doctor en Ciencias Económicas y Empresariales por la Universidad Complutense de Madrid. Profesor titular e investigador en el Departamento de Economía Financiera y Contabilidad de la Facultad de Estudios Empresariales y Turismo de Cáceres (Universidad de Extremadura-España). Máster en Dirección Financiera y Economía de la Empresa por la Universidad Complutense de Madrid. Actualmente es Decano de la Facultad de Empresa, Finanzas y Turismo de la Universidad de Extremadura.