Es a raíz del poder Visigodo cuando la ciudad pasa a llamarse Cesaracosta. También estuvo en poder visigodo un tiempo relativamente corto, si hablar de tres o cuatro siglos es hablar de poco tiempo, como veremos seguidamente.

En la ciudad, por aquélla época, convivían entre sí dos religiones: Cristiana y Judía. Los Cristianos, ya a comienzos del Siglo I d. de Cristo, se introdujeron en Hispania huyendo de las persecuciones de que eran objeto en Roma, a pesar de que también en Hispania eran perseguidos.

La religión dominante era la judía durante el dominio imperial, pero cuando pasó a manos visigodas fueron quedando en minoría para dominar el cristianismo. Los visigodos no tuvieron inconveniente en adoptar esta religión, sin embargo los Obispos y altos cargos eclesiásticos no les veían con buenos ojos, llegaron a llamarles "Herejes" ya que manipularon los Textos Sagrados a su manera al traducirlos a su lengua. De manera que, las enemistades y revueltas enfrentaban a tres religiones; Judíos (en clara minoría), Cristianos Católicos y Católicos Herejes (Visigodos).

Disputas que naturalmente se extendían en todo el territorio Hispano. Y revueltas que los propios Visigodos se veían impotentes de contener, pues no contaban con ejército suficiente para ello. Además estaban en guerra con los Francos quienes les asestaron un duro golpe en la batalla de Vouillé al derrotarles.

La tropa que quedó de aquélla batalla huyó hacia el sur ocultándose en los Pirineos. Pero los ejércitos francos les perseguían y tuvieron que seguir retrocediendo hasta encontrar la protección de las Murallas de Cesaracosta donde se hicieron fuertes.

El ejército franco llegó hasta las puertas de Cesaracosta con el propósito de hacerse con la plaza, tras arrasar otras más pequeñas a su paso. Esto ocurría sobre el año 541, cuando los Visigodos habían sido diezmados y entraban en fase de desaparecer de Hispania, aunque esto aún tardaría siglo y medio.

Las invasiones francas en Hispania provocaron una inmediata tregua en los enfrentamientos entre religiones que pactaron una alianza apoyada por la propia Iglesia. Continuaba no obstante, el dominio mayoritario de la Cristiano-Católica, cuyos seguidores se hacían llamar Católicos.

Los Francos arremetieron contra las Murallas de Cesaracosta, pero no fueron capaces de atravesarlas. Los intentos de asaltarlas acababan siempre en una matanza de los asaltantes al ser rechazados por los defensores.

Pero el ejército franco no quiso rendirse y renunciar a tan suculenta plaza, de modo que decidió doblegarla sitiándola. El importante número de soldados bloqueaba todas las puertas de la ciudad, y esperó pacientemente a que el hambre les obligase a salir; momento en el que aprovecharían para tomar Cesaracosta definitivamente. El sitio duraría entre dos y tres meses.

Sin embargo no contaban con el fervor religioso de sus habitantes quienes aprovecharon la situación para llevar a cabo un ayuno penitencial, racionando los alimentos de tal modo que podrían aguantar perfectamente otros tantos meses de asedio.

Tal vez se trate sólo de una leyenda, pero se dice que durante el asedio, los habitantes de la ciudad solían pasear por las almenas de la muralla la Túnica de San Vicente, reliquia a la que atribuían poderes milagrosos.

Muchos de los soldados francos, convertidos al Cristianismo, veían con temor la Túnica. Los propios oficiales sintieron también ese temor y creyeron que sería imposible doblegar a unas gentes protegidas por el propio Cielo.

Enviaron unos parlamentarios para acordar levantar el Sitio, siempre y cuando les entregasen una reliquia de tan venerada Túnica.

Parece ser que se consintió a ello, puesto que el sitio se levantó regresando el ejército a Francia.

Lo que el ejército Franco ignoraba, es que de haber aguantado más tiempo (poco) el asedio, se habría hecho con Cesaracosta sin la menor dificultad, pues el hambre ya era un hecho, al que se sumaron enfermedades y epidemias que se habían extendido en gran parte de la población.

Superado este asedio, volvieron los enfrentamientos entre religiones, sin que con ello terminasen de una vez por todas decidir qué religión debería ostentar el poder.

Cesaracosta no sólo tuvo que soportar el asedio Franco. También sufrió continuos ataques de los Vascones, aunque ninguno de ellos logró triunfar. Todos fueron rechazados.