Durante el período del reino visigodo la iglesia alzada sobre la tumba de los santos Justo y Pastor se convirtió en el centro de gravedad de Compluto, trasladada a sus cercanías mientras quedaba abandonada la vieja ciudad del Juncal. A lo largo del siglo VII, en especial una vez zanjado el cisma arriano, el culto a estos mártires se extendió por vastas regiones de la península como Toledo, Zaragoza, Sevilla o Mérida. En esta época están documentados templos consagrados a ellos en lugares tan alejados de Compluto como Astorga, Córdoba, Zaragoza, Medina-Sidonia (630), Guadix (652) o Alcázar de la Sal (682), esta última en el Algarve portugués, y también por entonces tuvo lugar la primera gran expansión de su culto de manos de san Fructuoso del Bierzo.

Fructuoso había nacido a principios del siglo VII en el seno de una noble familia visigoda, pero tras quedarse huérfano muy joven decidió renunciar a la corte abrazando la vida monástica. Tras estudiar en Palencia se retiró a las apartadas tierras del Bierzo, fundando hacia el año 640 un monasterio al que dio nombre de Compludo consagrándolo a los santos Justo y Pastor. No quedó ahí la labor de Fructuoso sino que, abandonando Compudo años después, comenzó a desarrollar una frenética actividad fundando al menos trece nuevos monasterios por toda la antigua provincia romana de Galicia y posteriormente por Lusitania y la Bética. Aunque se ignora si alguno de ellos, además del de Compludo, tuvo por titulares a los mártires complutenses, numerosas referencias indirectas indican sin ningún género de dudas que las fundaciones de san Fructuoso tuvieron como consecuencia la expansión de su culto por las actuales provincias gallegas y por Asturias, León y quizá también el norte de Portugal, lugares donde aún hoy en día existen multitud de lugares de culto (iglesias y ermitas) y numerosos topónimos, algunos de ellos de evidente origen medieval pero otros procedentes con toda probabilidad de esta remota época.

Aunque resulta difícil discernir en muchos casos si el inicio del culto a los Santos Niños en un lugar determinado tuvo lugar en la época visigoda o si, por el contrario, surgió a raíz de la repoblación cristiana en la Edad Media, cabe pensar que, al menos en las tierras del norte de la Península -Galicia, cornisa cantábrica, vertiente sur de los montes Cantábricos y norte de Portugal- en las que la invasión musulmana afectó muy poco a la vida cotidiana, si no todos, sí buena parte de los focos de devoción a los mártires complutenses puedan datar de tiempos de san Fructuoso.