El Santuario de Nuestra Señora de la Oliva fue una basílica visigoda, construida en el siglo VII, que con el paso del tiempo ha sufrido variaciones sustanciales, perdiéndose así quizás el recuerdo de aquella remota civilización.
En 1779 se construyó el edificio actual. Descubriendo unos cimientos en la ermita, se hallaron unos huesos y encima una columna; es un pedestal romano de gran peso con inscripción funeraria por una cara romana y que se aprovechó por su revés para grabar en ella la dedicación de la basílica. Esta columna se encuentra en el patio de entrada y en su parte izquierda.
La Ermita de la Oliva de Vejer es una obra de estilo neoclásico.
El retablo, realizado en 1753 es de estilo barroco. En su interior se encuentra una talla de Jesús Crucificado “Cristo de la Oliva”. Esta magnífica imagen del siglo SVIII de la escuela genovesa; de madera tallada y policromada, de estilo barroco se atribuye a Francesco María Maggio (Génova 1705- Cádiz 1780). La importancia de este Crucificado estriba, entre otras razones, porque marca el unto de inflexión o tránsito entre los crucificados andaluces y los que realizan los maestros genoveses en Cádiz.
En 1799 se levanta el magnífico retablo de madera y policromía, de magnífica ejecución y ensamblajes. En su centro el camarín de la Patrona de Vejer, Ntra. Sra. De la Oliva, muy deteriorado.
La imagen actual de la Virgen fue construida en el año 1595 por Martín Alonso de Utrera por encarto del vejeriego Lorenzo Patiño. Es una magnífica talla policromada que por su estilo pertenece a la escuela Andaluza de Imaginería, de la mejor época de la escultura religiosa española.
Otras imágenes que se encuentran en el interior del templo: Imagen de Santa Ana y la Virgen Niña, talla en madera policromada de finales del siglo XVI; Imagen de San Isidro Labrador; Imagen de San Antonio; Santos Patronos San Servando y San Germán.
