Este mito se originó en el siglo XII, cuando los Moros atacaron y conquistaron la ciudad de Mérida, en España. Se narra que siete obispos abandonaron la ciudad con maravillosas reliquias e inmensos tesoros y que se escondieron más allá del mundo conocido. Comenzó a correr el rumor de que cada uno de ellos construyó una fantástica ciudad en una tierra lejana, más allá del Mar Océano, como era llamado el Océano Atlántico. Estas ciudades eran distinguidas con los nombres de Aira, Anhuib, Ansalli, Ansesseli, Ansodi, Ansolli y Con. Por mucho tiempo se pensó que las siete ciudades estaban situadas en Antilia, la legendaria isla situada en el MarOcéano.
El origen del nombre Antilia puede derivar de la Atlántida descrita por Platón en el Timeo y Crizia o quizá del latín anterior en cuanto es considerada anterior al Cipango descrito por Marco Polo. Plutarco, en sus Vidas Paralelas, escribió que el cónsul español Quinto Sertorio tuvo contacto con algunos navegantes que afirmaron haber avistado unas islas a aproximadamente cuarenta días de navegación desde Marruecos. El erudito PaolodalPozzoToscanelli las dibujó a unas 700 leguas (3500 kilómetros) de las costas españolas, dándoles una exacta ubicación en el Mar Océano.
En los tiempos de Cristóbal Colón tenían la convicción de que las sietes ciudades estaban situadas en Antilia. Sucesivamente comenzó a pensarse que estaban situadas en Norte América. La primera expedición que llegó a los actuales Estados Unidos meridionales tuvo lugar en el 1528, al mando de Panfilo de Narváez. La empresa se enfrentó con enormes dificultades ambientales y además hubo continuos enfrentamientos con los nativos guiados por el Cacique Hirrihigua. Casi todos los que viajaron murieron, excepto Alvar Nuñez Cabeza de Vaca, Alonso del Castillo Maldonado, Andrés Dorantes de Carranza y un esclavo bereber llamado Estebanico.
Los cuatro se alejaron lo más que pudieron de esos lugares tan hostiles avanzando hacia el oeste en los actuales estados de Alabama,
Louisiana y Texas. Su increíble viaje duró unos ocho años, durante los cuales conocieron varias tribus indígenas, logrando sobrevivir. Llegaron finalmente a Culiacán, en Sinaloa, territorio que hacía parte de la Nueva España, contando haber visto enormes riquezas.
Alvar Nuñez Cabeza de Vaca escribió un libro en donde narró la aventura, titulado “Naufragios”. En este libro se describieron ciudades de oro y riquezas sin límites, y rápidamente comenzó a pensarse que el territorio atravesado por cuatro aventureros fuera el reino de las siete ciudades, que se llamaron “de Cíbola“, porque anticamente el bisonte, numeroso en las praderas norte-americanas, se denominaba “cibolo”.