Posiblemente, Ciella fuese la ciudad de Gella, una de las 17 ciudades Vacceas. Ciella estaría dentro del territorio Vacceo, justo en la frontera con los Arévacos, que aunque pueblos amigos, eran diferentes. Antes de los romanos, ya existía la ruta que venía de Sagunto (Valencia), y atraviesa la Península Ibérica. A través de dicha ruta, bajaban los minerales que extraían en la provincia de León y que luego iban a Grecia, Egipto, etc. Esta ruta es la que pasaba por Ciella y allí en la ciudad de Ciella, estaba el santuario a la diosa "Gella", el cual fue creado por los celtas que allí habitaban. Estos celtas, cuando entraron en Ibería, se asentaron en los lugares que controlaban las vías de comunicación, luego en algunos sitios construían pueblos guerreros, donde se entrenaban para luego contratarse como mercenarios. Ellos fueron los protagonistas principales de las batallas de Sicilia entre cartagineses y romanos. combatieron con los cartagineses y de ellos adquirieron la costumbre de adorar a la diosa madre.
En el municipio se han reconocido como vestigios más antiguos diferentes restos de la época romana. Este territorio era atravesado por una de las vías que unía Clunia con el valle del río Arlanza, encontrándose en su recorrido la villa de Ciella. Otros hallazgos de cruces y estelas dan constancia de la posible existencia de una pequeña comunidad hispanovisigoda en Valdeande.
Valdeande también estuvo presente en la Reconquista ya que la torre de la iglesia formaba parte de las fortificaciones levantadas en esa época en el valle del Esgueva. El pueblo de pressura que se adelantó a la reconquista, fue el de Villajimeno, y luego ya el conde Gonzalo Fernández, el padre de Fernán González, creó su pueblo, este de Val-de-Fández, es decir Val de Fernández. En lo alto de la montaña construyó su castillo, el cual posteriormente fue destruido por Almanzor.
Ahora bien, el primer documento escrito en que se cita a Valdeande aparece en el año 1037, tratándose de un manuscrito de la época de Fernando I de Castilla. Se donó el monasterio de Ciella a Silos, pero la importancia del monasterio de Ciella, era que poseía las reliquias de San Pelayo, las cuales fueron donadas en 1039 al de San Pedro de Arlanza, para hacerle grande.
En el Censo de Vecindarios de la Corona de Castilla realizado en 1591 se denominaba del mismo modo y pertenecía al Partido de los Arauces, incluida en la provincia de Burgos. El partido contaba con 876 vecinos pecheros.
Villa perteneciente a la Jurisdicción de Los Arauzos, de realengo, en el partido de Aranda de Duero, con Alcalde Ordinario.