Está situada en la calle de sus mismo nombre[1] en un área antiguamente situada a extramuros de la ciudad.
Según una leyenda, la ermita goza con la presencia de una imagen de San Eufrasio de iconografía bizantina que perteneció a la iglesia andaluza de Andújar; dicha imagen fue escondida para no ser ultrajada por los moros en 711 durante la invasión sarracena, fue posteriormente encontrada en 1227 en un hueco de Sierra Morena y trasladada a Tudela.
Esta primera ermita dedicada a Nuestra Señora de la Cabeza fue fundada en 1611.
Estaba situada en un emplazamiento diferente al de la actual ermita, en concrento al pie del monte del Castillo de Santa Bárbara, junto a la Iglesia de Santísima Trinidad.
Fue destruida en 1808 durante la Guerra de Independencia.