La primera construcción sobre el lugar de la que tenemos noticias fue un conjunto epigráfico-monumental funerario romano, fechado en el siglo II d.C. en memoria de MARCUS DOMITIUS PROCULUS, fallecido a los diecisiete años, y levantado por su padre, MARCUS DOMITIUS SERANUS, según se desprende de las inscripciones localizadas en el interior y exterior de la ermita. Su adscripción al ámbito funerario romano fue apuntada en un primer momento por Agustín Ventura en 1975, seguida de los respectivos estudios de Ferrán Arasa i Gil, de la Universidad de Valencia, en 1983 y 1987.

Se conserva el paramento derecho del edificio que coincide con el segundo tramo de la ermita y forma parte del muro contiguo a la hospedería, apreciándose claramente desde ésta última sus sillares y molduras.

Restos de columnas, capiteles y lápidas del conjunto monumental que aparecen en las esquinas del muro oeste de la ermita, son elementos arquitectónicos de gran envergadura que denotan la importancia del lugar. Asimismo, aparecen dos estelas funerarias iberas, una en el interior y otra en el exterior de la Ermita, ya que el conjunto al completo se incluye en el exterior del recinto fortificado de época ibérica.

J. Salvador, quien ya dio noticia en 1890 de los restos arquitectónicos de la Ermita de la Virgen del Cid, recoge la información que proporciona A. Piera en 1712 sobre la mencionada ermita, según la cual la primera referencia escrita y existente sobre la “Iglesia del Cid” es del año 1195, en un documento de donación del rey Alfonso II de Aragón a Gastón, maestre de la Orden de San Redentor, territorio que posteriormente configuraría la Baylía de Cantavieja. La misma Iglesia del Cid vuelve a aparecer en la carta puebla de Cantavieja, concedida por el monarca Pedro II en 1212. Esta referencia litúrgica podría estar indicando la existencia de un edificio anterior a la conquista cristiana.

Durante el siglo XIV o principios del XV se edificó la primera ermita, de estilo gótico. Era de menores dimensiones que la actual y su volumen puede observarse en el muro oeste de la misma. Estaba compuesta por una sola nave dividida en tres tramos más el coro y cubierta por bóvedas de crucería. Según inscripción sobre piedra reutilizada del mausoleo romano y situada en el ángulo noroeste de la ermita, se efectuó una remodelación en 1546, que amplió la ermita hacia el norte y transformó el ábside gótico, quedando una cabecera recta con girola central delante del altar y dos corredores enrejados que dan paso a la capilla situada detrás de la cabecera, la capilla dedicada al Santo Cristo Milagroso, construida en 1728.