Villaviciosa se fue formando en el cruce de caminos Córdoba-Noroeste y Sevilla-Toledo tras la llegada de la imagen de la imagen de la Virgen Nuestra Señora de Villaviciosa, de la cual adquirió el nombre.

Según cuenta la leyenda, la imagen fue traída desde un lugar de Portugal llamado Vila Viçosa (el Alentejo) "cercano al palacio donde tenia su residencia el duque de Braganza" hasta nuestro pueblo por el vaquero castellano Hernando. Según nos cuenta Ángel Fernández Dueñas, la imagen fue hurtada por Hernando en su ermita de Portugal, "Hernando se afligía del descuido y pobreza que rodeaban a la Señora (...). Y decidió rescatarla de su abandonada ermita" . "Compadecido un día de tan triste estado, entró de noche en la ermita, tomando la imagen y poniéndola en su zurrón emprendió una larga marcha que no cesó hasta llegar al pago de Las Gamonosas, cerca de Espiel, jurisdicción de la ciudad de Córdoba, dedicada al pasto de los ganados del común y después a dehesas de yeguas" . Depositó a la imagen en el hueco de un alcornoque . Los portugueses tras darse cuenta que la imagen había sido robada corrieron a buscarla y llegaron hasta el alcornoque donde estaba colocada, y, junto a ella Hernando. Tras capturarlo y recuperar a la Virgen, volvieron hacia Portugal. Hernando fue encarcelado, pero tras escaparse de la prisión (se piensa que fue un milagro de la Virgen) volvió a recuperar a la imagen y, como antes, la trasladó a su emplazamiento en el hueco del alcornoque. Otra vez, tras perseguirle y apresarle, los portugueses creyeron que la voluntad de la imagen era la de quedarse en su emplazamiento serrano (lugar donde Hernando la había traído), dieron todo el dinero que tenían a Hernando, para que construyera una ermita digna a la imagen. Así se piensa que fue cómo se levantó la primera construcción en el lugar.