Наиболее ранние упоминания о базилике Евлалии, построенной над могилой мученицы, содержатся в гимнах Пруденция и в хронике Идация, епископа города Аквы Флавиевы (ныне Шавеш, Португалия). Епископ Идаций (ум. около 468 г.) под 429 г. упоминает о гибели некоего вандала, посягнувшего на гробницу Евлалии, а под 456 г. сообщает о видении мученицы королю вестготов Теодориху II (453–466 гг.), который намеревался разграбить Эмериту. По данным археологических раскопок, в IV в. над могилой Евлалии был возведён прямоугольный в плане мартирий с апсидой и крытой папертью. В первой половине V в. на месте мартирия была сооружена монументальная трёхнефная базилика, ставшая центром паломничества. В храме находилась усыпальница епископов Эмериты. Около 560 г. по повелению епископа Фиделия базилику перестроили. При епископе Масоне (около 570 – около 606 гг.) по молитвам к Евлалии Лузитания была избавлена от эпидемии. Епископ Масона основал в Эмерите больницу (xenodochium), медицинскую службу для паломников, в базилике Евлалии разрешил выдавать денежные кредиты. По повелению вестготского короля Леовигильда (569–586 гг.) особая комиссия расследовала обстоятельства конфликта между православными и арианами за владение базиликой и отдала её православным. После этого король приказал Масоне передать арианскому епископу Сунне тунику Евлалии, однако тот отказался выдать святыню, за что был изгнан (582 г.), но через три года возвращён на кафедру после того, как королю явилась Евлалия. Сохранился гимн мученице, приписываемый Исидору Гиспальскому (Севильскому) и впоследствии вошедший в состав литургии испано-мосарабского обряда (Laudem beatae Eulaliae). После захвата Эмериты арабским полководцем Мусой ибн Нусайром (713 г.) богослужения в базилике Евлалии прекратились, храм был заброшен и начал разрушаться. По повелению короля Сило (774–783 гг.) мощи Евлалии были перенесены в Астурию, в королевскую резиденцию (ныне селение Сантьянес, близ Правии). Там был сооружён храм в честь святого Иоанна, в который положили мощи мученицы. Король Астурии Альфонс II (791–842 гг.) перенёс резиденцию в город Овьедо. Мощи Евлалии были помещены в дворцовую часовню святого Михаила (Камара Санта), которая впоследствии стала частью кафедрального собора Спасителя. Король Леона Альфонс VI велел поместить мощи в серебряный реликварий (1075 г.). Евлалия стала наиболее почитаемой в Астурии святой. С 1617 г. в Овьедо действовало братство, основанное в честь мученицы. В 1639 г. Евлалия была объявлена покровительницей города и епископства Овьедо. К кафедральному собору пристроили капеллу в стиле платереско, куда перенесли мощи мученицы. В 1229 г. король Леона Альфонс IX отвоевал Мериду и воздвиг на месте обветшавшей базилики Евлалии новый храм в романском стиле. Город стал центром духовно-рыцарского Ордена святого Иакова (см. Сантьяго), члены которого особо почитали Евлалию.