Malajscy marynarze widzieli orzechy coco de mer „spadające w górę” z dna morskiego i stąd wywnioskowali, że orzechy te muszą rosnąć na podwodnych drzewach, w lesie na dnie Oceanu Indyjskiego. Według Antonio Pigafetty i Georga Eberharda Rumphiusa, Malajowie wierzyli, że drzewo to jest również domem ogromnego ptaka lub ptakopodobnego stworzenia Garudy (lub Rukh Arabów). Afrykańscy kapłani wierzyli, że Garuda jest w stanie polować na słonie i tygrysy. Afrykańscy kapłani wierzą również, że czasami drzewa coco de mer wznosiły się ponad powierzchnię oceanu, a kiedy to się działo, fale, które drzewa tworzyły nie pozwalały żadnemu statkowi w pobliżu odpłynąć, a bezradni marynarze byli zjadani przez Garudę.
Orzechy, które znajdowano w oceanie i na plażach nie miały już łupiny i przypominały rozczłonkowaną dolną część ciała kobiety, w tym pośladki. To skojarzenie jest odzwierciedlone w jednej z roślin archaicznych nazw botanicznych, Lodoicea callipyge Comm. ex J. St.-Hil., w którym callipyge jest od greckich słów oznaczających „piękny zad”. Historycznie te pływające „piękne zadki” były zbierane i sprzedawane za fortunę w Arabii i w Europie.
Na Malediwach, wszelkie orzechy coco de mer, które zostały znalezione w oceanie lub na plażach miały być oddane królowi, a zachowanie orzecha dla siebie lub jego sprzedaż mogła skutkować karą śmierci. Jednak Rudolf II, Święty Cesarz Rzymski, był w stanie kupić jeden z tych orzechów za 4 000 złotych florenów. Holenderski admirał Wolfert Hermanssen również otrzymał orzech jako prezent za swoje zasługi, od sułtana Bantam w 1602 roku, za walkę z Portugalczykami i ochronę stolicy Bantam. Jednak w orzechu, który otrzymał admirał, brakowało górnej części; najwyraźniej sułtan nakazał odciąć wierzchołek orzecha, aby nie naruszyć skromności szlachetnego admirała. João de Barros wierzył, że coco de mer posiada niezwykłe właściwości lecznicze, przewyższające nawet właściwości „kamienia szlachetnego Bezoar”. Dr Berthold Carl Seemann w jednej ze swoich książek wspomina, że wielu wierzyło, iż orzechy te są antidotum na wszystkie trucizny. Orzechy były chwalone nie tylko przez naukowców i botaników, ale również przez poetów. Luís de Camões napisał:
O’er lone Maldivia’s islets grows the plant,
beneath profoundest seas, of sov’reign might,
whose pome of ev’ry Theriack is confest,
by cunning leech of antidotes the best
W 1769 roku Jean Duchemin popłynął na Praslin, drugą co do wielkości wyspę Seszeli, na statku L’Heureuse Marie. Załadował się tam ładunkiem tych niezwykłych orzechów, które później sprzedawał na indyjskich rynkach. Po jego wyprawie orzechy coco de mer nigdy już nie miały tak niezwykłej wartości.