À l’origine, Antilia est une île mythique localisée dans l’Océan Atlantique, à l’ouest de l’Espagne, et qui a donné son nom aux Antilles. Son étymologie est incertaine. Elle a été rapprochée d’Atlantis, le fameux continent imaginaire situé au-delà des colonnes d’Hercule dans le Timée de Platon, mais elle pourrait aussi être dérivée du latin anterior et signifierait alors l’île située avant Cypango, la grande île des Indes. On peut également identifier deux mots portugais, anti-ante (avant) et illa, une forme archaïque du portugais ilha (île), ce qui pourrait donner « l’île avant », c’est-à-dire à l’avant de l’Europe, et située avant le continent qui était supposé être l’Asie.

Au Moyen Âge, Antilia est associé au mythe des « Sept cités ». Quelques îles fantastiques de l’Océan occidental avaient été dédiées à Saint Brendan ou à Saint Malo selon des légendes qui remontaient jusqu’au VI^e siècle, mais c’est une autre légende qui eut cours en Europe dès le XI^e. En 743, sept prêtres et leurs fidèles auraient pris la mer pour fuir la conquête arabe de la péninsule ibérique. Afin d’établir s’il s’agissait d’une réalité historique, le roi du Portugal Alphonse V missionna une expédition en 1475 pour retrouver cette île. Son successeur, le roi Jean II, envoya à son tour une expédition qui partit de Lisbonne en 1487 mais ne revint jamais.

Le nom Antillia apparaît sur les cartes marines et les mappemondes au XV^e siècle, notamment sur le globe de Martin Behaim (1491-1493), ainsi que sur l’atlas d’Andrea Bianco (1436). La carte du Vinland (1434) indique une île nommée « Antilia » située au nord d’une autre île nommée « île de Branzilæ », de même que la carte marine de Pizzigano (1424). Cette île était désignée en 1474 par le savant florentin Paolo Toscanelli, dans les lettres qu’il adressait à la cour de Portugal et à Christophe Colomb, comme l’une des étapes sur la route de Lisbonne aux Indes par l’ouest. Une carte dessinée de sa main montrait la distance de Lisbonne au port chinois de Quinsay, jalonnée par les grandes îles d’Antilia et de Cypango.  Le nom de cette dernière, qui correspondait au Japon, était familier en Europe grâce aux récits de Marco Polo. Elle était considérée comme la dernière terre connue de l’Orient, Antilia étant quant à elle la dernière terre connue de l’Occident. Inspiré par la carte de Toscanelli, Christophe Colomb était convaincu de pouvoir rejoindre les Indes par l’Ouest, et il devait bien savoir également qu’il trouverait sur sa route la mythique île d’Antilia.