Malay marinheiros tinham visto o coco de mer “caindo para cima” do fundo do mar, e assim eles tinham raciocinado que estas nozes devem crescer em árvores subaquáticas, em uma floresta no fundo do Oceano Índico. Segundo Antonio Pigafetta e Georg Eberhard Rumphius, o povo malaio acreditava que a árvore era também o lar da enorme ave ou criatura parecida com pássaro Garuda (ou Rukh dos árabes). Os padres africanos acreditavam que os Garuda eram capazes de caçar elefantes e tigres. Os padres africanos também acreditavam que às vezes o coco de mer árvores se elevava acima da superfície do oceano, e quando isso acontecia, as ondas que as árvores criavam não permitiam que nenhum navio nas proximidades navegasse e os marinheiros indefesos eram comidos pelos Garuda.
As nozes que foram encontradas no oceano e nas praias já não tinham casca, e assemelhavam-se à parte inferior desmembrada do corpo de uma mulher, incluindo as nádegas. Esta associação se reflete em um dos nomes botânicos arcaicos da planta, Lodoicea callipyge Comm. ex J. St.-Hil., no qual calipyge é das palavras gregas que significam “alcatra bonita”. Historicamente, estes “belos côcos” flutuantes eram recolhidos e vendidos por uma fortuna na Arábia e na Europa.
Nas Maldivas, qualquer coco de mer nozes que eram encontrados no oceano ou nas praias era suposto ser dado ao rei, e guardar uma noz para si ou vendê-la poderia ter resultado na pena de morte. No entanto, Rudolf II, Santo Imperador Romano conseguiu comprar uma destas nozes por 4.000 florins de ouro. O almirante holandês Wolfert Hermanssen também recebeu uma noz como presente pelos seus serviços, do Sultão de Bantam em 1602, por combater os portugueses e proteger a capital de Bantam. No entanto, faltava a parte de cima da noz que foi dada ao almirante; aparentemente o Sultão tinha ordenado que a parte de cima da noz fosse cortada, para não perturbar a modéstia do nobre almirante. João de Barros acreditava que o coco de mer possuía espantosos poderes curativos, superiores até aos da “pedra preciosa Bezoar”. Em um de seus livros, o Dr. Berthold Carl Seemann mencionou que muitos acreditavam que as nozes eram um antídoto para todos os venenos. As nozes foram elogiadas não só por cientistas e botânicos, mas também por poetas. Luís de Camões escreveu:
As ilhotas das Maldivia cultivam a planta,
baixo dos mares mais profundos, do reino sov’re might,
quela cúpula de Ev’ry Theriack é confestada,
por sanguessugas de antídotos os melhores
Em 1769, Jean Duchemin navegou até Praslin, a segunda maior ilha das Seychelles, no navio L’Heureuse Marie. Ele carregou com uma carga destas nozes incomuns, que mais tarde vendeu nos mercados indianos. Depois da sua viagem, coco de mer nuts nunca mais teve o mesmo valor extraordinário.