Según la «historia Sacra», escrita por el P. Fr. Diego de Carmona Bohórquez, la imagen de la Virgen de Regla, fue mandada a construir por el mismo San Agustín, doctor de la Iglesia, siendo obispo de Hipona (Norte de África). El santo tenía la imagen en su oratorio.

Trece años después de la muerte de San Agustín (443), Hipona era atacada por los Vándalos, porque el diácono San Cipriano y otros monjes de la orden de los agustinos se vieron obligados a escapar a España. Al llegar colocaron la imagen frente al mar. Allí creció la devoción, llegando a ser el monasterio de Regla.

La imagen de Nuestra Señora de Regla, según se cree, siempre fue de color negro. Así nos recuerda a los Cantares de Salomón: «Negra soy, pero hermosa hija de Jerusalén».

En el siglo VIII los monjes tuvieron que huir por la invasión de los moros y ocultaron la Ntra. Sra. de Regla cerca del monasterio. En el siglo XIII, tras la victoria de Alfonso el Sabio, la Santísima Virgen, en una visión a un canónigo regular de la Catedral de León, le mostró el lugar donde se hallaba enterrada su imagen y le pidió que viniese a desenterrarla para retornarla a su antiguo santuario. El canónigo obedeció y, cuando se encontraba en el lugar y descansando bajo una higuera, escuchó una voz angelical que del centro de la tierra le decía:

«Este es mi lugar», voz que repitiéndose, confirma al canónigo la dulce esperanza que traía en su peregrinación, de encontrar la imagen. Trabaja con entusiasmo y fe en el sitio, y «¡Oh portento!» (Exclama en su narración el Fr. Tomás de Harrera.)Encuentra el depósito sagrado y la lámpara encendida, conservándose hoy un cáliz de los que con Nuestra Madre y Señora estuvieron enterrados. Se restituye a la Señora a su propio templo, y se labra una pequeña capilla en el sitio. Del maravilloso encuentro que hoy existe, así como la higuera y la cisterna, conociéndose este lugar como Humilladero. Desde este tiempo ha continuado Ntra. Señora de Regla en el Santuario abordada por todos, y siendo la admiración general por los muchos dones que siempre dispensará a los fieles que la imploran en sus aflicciones.

Algunos dicen que el nombre de «La Virgen de Regla» es por razón de ser ella quién custodia la regla de los frailes Agustinos. Esto no es de extrañar ya que el mismo San Agustín era un gran devoto de la Virgen María. También se sabe que Don Alonso Pérez de Guzmán alzó en Chipiona el Castillo de Regla.