La ermita de la Virgen de la Oliva, en Vejer de la Frontera, es uno de los edificios religiosos en culto más antiguos de España. De hecho, el cristiano español más antiguo de nombre conocido era de Vejer y se llamaba Firmo, un soldado que fue martirizado en tiempos del emperador Diocleciano (años 284-305), según tradición recogida por Fray Gerónimo de la Concepción.
Se cuenta que San Hiscio o Esicio fue uno de los Siete Varones Apostólicos que vinieron a España, entrando por el Sur. Era discípulo de Santiago Apóstol y, como cuenta el Padre Flórez, se asentó primero en Carteya como obispo pero luego trasladó su sede a Medina Sidonia en la década de los sesenta del siglo I. Se ignora quiénes fueron sus sucesores.
Ahondando en "tradiciones históricas fiables", alguna leyenda dice que Santiago vino a Cádiz en el año 36 para permanecer seis años en Hispania. Dejó aquí a su discípulo Basileo como obispo, pero éste pasó luego a Oporto y finalmente fue martirizado en Plasencia en el año 60. Su sucesor sería San Esicio.
La introducción del cristianismo en Cádiz debió ser temprana pero tardó en producirse su asentamiento, debido a la preponderancia en este territorio del culto a Hércules. Más bien sería zona de paso hacia el Norte, siguiendo la ruta que utilizaba la Legio VII Gemina.
En esta ermita fueron descubiertos restos romanos, que nos indican la existencia previa de una villa, cuyos materiales se reciclaron para la construcción del templo cristiano Se puede hablar de una construcción paleocristiana con precedentes muy antiguos de ocupación continuada que se extiende hasta la misma Prehistoria.
Una leyenda sitúa su fundación en el siglo IV debida a San Paulino de Nola o a sus dos discípulos Paulino y Ambrosio. Una lápida del año 644 añade a estos otros tres también martirizados. Vicente, Félix y Julián. Es un templo coetáneo de las próximas iglesias de San Paulino y San Ambrosio, fundada por los mismos de la Oliva. La basílica de los Santos Mártires en Medina Sidonia pudo ser también de igual fundación.
En época visigoda el edificio fue consagrado por el obispo Teodoracio. Tras la incorporación de Vejer a la Corona de Castilla, la ermita se reconstruyó en el siglo XIV. Como testigo de ello, en un muro lateral del patio hay un pequeño vano mudéjar con arco conopial labrado en piedra y decorado con cerámica vidriada.
Durante unas obras de cimentación en 1779, 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 en el año 674. Esta columna se encontraba en el patio de entrada y ahora ha sido trasladada al interior del templo. Los restos óseos y cenizas se dice que son del protomártir Esteban, de los santos mártires gaditanos Servando y Germán y de las sevillanas Justas y Rufina.
La imagen de la Virgen de la Oliva es obra del escultor utrerano Martín Alonso de Mesa realizada en 1596. La imagen de Santa Ana y la Virgen Niña es de mediados del siglo XVII. También están las imágenes de San Isidro Labrador, de San Antonio y de los Santos Patronos San Servando y San Germán. Dos pinturas del XVII, debidas al mejicano Juan Correa, representan a San José y a San Juan Bautista.
El templo actual, de estilo neoclásico, fue muy remodelado en 1779 con cánones relacionados con Torcuato Cayón. En fechas recientes se han hecho obras de ampliación. El retablo barroco está fechado en 1763 y reformado en el siglo XIX. En su interior se encuentra el Cristo de la Oliva, imagen barroca del siglo XVIII de la escuela genovesa. De madera tallada y policromada, se atribuye a Francesco María Maggio (Génova 1705- Cádiz 1780). La importancia de este Crucificado estriba en que marca el tránsito entre los crucificados andaluces y los que realizan los maestros genoveses en Cádiz.
Tratándose de la Oliva, no dejamos de señalar que el jardín que se extiende por delante de la ermita está flanqueado, a uno y otro lado, por sendas hileras de olivos silvestres o acebuches. Destacan especialmente dos troncos de tamaño considerable que han estado secos durante mucho tiempo pero en la primavera de 2024 han rebrotado con más o menos intensidad. Los lugareños le atribuyen una antigüedad a uno de mil años y a otro, de setecientos años
En esta ermita se hace anualmente una romería que concentra a gran número de vejeriegos en el mes de mayo.