A lenda da Ilha de S. Brandão, transmitida oralmente, tornou-se popular, aproximadamente, a partir do século X, quando um anónimo, provavelmente, um monge irlandês, escreveu o livro Navigatio Sancti Brandani, onde se relata a existência de uma ilha, descoberta por S. Brandão, que considerava ser o Jardim do Éden.
São Brandão nasceu em 484 d.C., em Tralee, na região de Kerry, na Irlanda. Foi baptizado e educado pelo bispo Erc de Kerry. Tornou-se abade, fundou vários mosteiros e morreu em 577, em Annaghdown (Eunachdunne), condado de Galway. É através das suas viagens marítimas, em busca do Paraíso, que S. Brandão se tornou célebre na História e na literatura como "Brandão, o Navegador".
A versão mais conhecida da história da Ilha de S. Brandão foi escrita por Benedeit, por volta de 1130, no capítulo "Navegação de S. Brandão à procura do paraíso" do seu livro Paraíso. Conta-se que S. Brandão terá pedido a Deus para ver o Paraíso e o Inferno e, após a sua fuga e a dos restantes monges aos invasores Normandos, S. Brandão e os monges (em número que variava entre 18 a 300 pessoas) iniciaram uma viagem, que durou sete anos, em busca do Paraíso. A lenda narra várias aventuras fantásticas, como aquela em que encontrou uma baleia em cima da qual rezou, mantendo-se em comunhão com Deus. Em seguida, atracaram na Ilha dos Pássaros, onde ficaram durante dois meses e onde se aprovisionaram de mantimentos, partindo depois rumo ao Oriente. Após quarenta dias, em alto mar, sem avistar terra, deparam com um grande muro de nevoeiro que circundava o que pensavam ser a ilha do Paraíso e que impedia os descendentes de Adão de entrar. Com a ajuda e a permissão de Deus (caso contrário seria impossível franquear a entrada que estava aberta no espesso nevoeiro), seguiram nesse caminho durante três dias até que ao quarto dia avistam o Paraíso, envolto numa parede mais branca do que a neve e cravejada de pedras preciosas: topázios, calcedónias, jacintos, esmeraldas, jaspe, ametistas e cristais, entre outras. Montes de mármore, batidos pelo mar, precediam uma montanha de ouro fino que, por sua vez, dava lugar aos muros do paraíso que delimitavam o jardim. A entrada, guardada por dragões brilhantes como o fogo, abriu-se para deixar passar um mensageiro de Deus. Um belo jovem acolheu-os, nomeou-os pelos seus nomes verdadeiros e beijou-os com carinho, antes de acalmar os dragões, que depois se deitaram humildemente sem resistência. À ordem do jovem guia, um anjo abriu a porta e os monges entraram no Paraíso guiados pelo jovem que lhes mostrou as árvores, os rios, as flores, os frutos, os perfumes (que pairavam no ar de um doce e eterno Verão), os bosques cheios de animais de caça e a enorme abundância de peixes, num local que não conhecia pobreza, dor, doença, fome e sede.
S. Brandão, felicíssimo por se encontrar ali, foi levado pelo jovem a um monte alto, onde lhe foram descritas as recompensas destinadas a cada um e onde ambos observaram maravilhas que nenhum homem pode compreender, contemplaram também os anjos que se alegravam por recebê-los e ouviram melodias. Em seguida, o jovem guia aconselhou os monges a regressar, já que estes não podiam adquirir mais conhecimentos sobre o Paraíso e sobre as suas glórias futuras, porque ainda eram de carne e osso. A Revelação seria feita quando voltassem, em espírito, para o seu julgamento. Antes da partida, S. Brandão e os monges receberam pedras de ouro como recordação e como forma de lhes incutir coragem.
Na época dos Descobrimentos, ainda se perseguia o sonho de ilhas fantásticas, das quais a Ilha de S. Brandão, também chamada Ilha Perdida, era disso exemplo. A Ilha de S. Brandão manteve-se na cartografia dos séculos XIII ao XIX e, à medida que os conhecimentos do oceano avançavam, a ilha ia sendo deslocada para paragens mais remotas. A Ilha de S. Brandão surge na carta Dulcert de 1339, no local onde, em 1350, no Atlas Mediceu, aparece a ilha da Madeira.
As imagens do Jardim do Éden associam-se a outras lendas fantásticas e mitológicas, das quais se destacam, ainda, o mito de Atlântida, o jardim das Hespérides, a Antília (ou das Sete Cidades), as lhas Afortunadas, o Brasil, entre outros.
De missionário a viajante marítimo, S. Brandão tornou-se num aventureiro e num descobridor, creditado pelo folcore, que o relacionou com as fábulas e com as sagas dos povos da costa ocidental irlandesa. De referir ainda, que dois investigadores árabes, Goeje e Asín, consideraram haver analogias entre a Navigatio e as viagens de Simbad, o Marinheiro, que integra o livro das Mil e Uma Noites.
