Las ruinas de la iglesia visigoda de Valdecebadar (siglos VI-VII d.C.) está situada en las cercanías de la Rivera de Olivenza. Por desgracia, Valdecebadar no es un edificio, sino sólo una planta de edificio, apenas una estructura esbozada en el suelo, restos de muros de escasa de altura. Cualquier vestigio de decoración, columnas, pilastras, etc., desapareció hace ya mucho tiempo y sólo la planta y algunos elementos de cimentación y soporte permiten deducir las características originales.

El hallazgo se realizó en 1967/68. En aquel tiempo se trazó un plano indicando la posición de algunas estructuras de cimentación, una pila bautismal de inmersión, y un conjunto de tumbas en el interior y en los alrededores, hechas con ladrillos y tégulas, características de los enterramientos tardoromano-visigodos. Otro detalle extraño en Valdecebadar es la posición de la única puerta de acceso identificada, al extremo Sur del crucero, rasgo atípico en una iglesia por otra parte calificada sin dudas como visigótica. Hay referencias de que el suelo es de opus signinum y bien conservado, pero precisamente el recubrimiento protector no permite verlo.

El edificio tiene planta de cruz griega, con una longitud de brazos de unos 18 metros, cruz casi perfecta dada la aversión de los constructores medievales por los ángulos rectos. De la figura básica de cruz griega de la planta, emergen tres cuerpos: Hacia el Este un ábside con trazado exterior e interior ultrasemicircular, en forma de herradura muy cerrada, sobrepasada en 1/3 de radio, donde se situaba el presbiterio. Ante éste se han encontrado las huellas de un cancel, y dentro, las huellas de las cuatro columnas que soportaban la mesa de altar.

En el muro Este del brazo Norte de la cruz se abre el acceso a una estancia cuadrada, de dimensiones similares a cualquiera de los cuatro brazos de la cruz que ocupa el hueco Nordeste de la cruz. En esta habitación se halló una pila bautismal de inmersión con dos pequeños tramos de escalera de entrada y de salida de tres gradas, pues el ritual de bautismo era de inmersión de adultos. Curiosamente, esta estancia no aprovecha el muro Norte del brazo Este de la cruz, sino que tiene su propio muro Sur.

El tercer cuerpo es otra estancia cuadrada de dimensiones casi idénticas a la anterior, y utilización desconocida, que ocupa el hueco Sudeste de la cruz. A ella se accede por el muro Sur del brazo Este de la cruz base. Es una especie de sacristía que, al igual que antes, tiene su propio muro Oeste de cierre, en vez de utilizar el muro Este del brazo Sur.