Los marineros malayos habían visto nueces de coco de mer «cayendo hacia arriba» desde el fondo del mar, por lo que habían razonado que estas nueces debían crecer en árboles submarinos, en un bosque en el fondo del océano Índico. Según Antonio Pigafetta y Georg Eberhard Rumphius, los malayos creían que el árbol era también el hogar del enorme pájaro o criatura parecida al pájaro Garuda (o Rukh de los árabes). Los sacerdotes africanos creían que el Garuda era capaz de cazar elefantes y tigres. Los sacerdotes africanos también creen que a veces los árboles de coco de mer se elevaban por encima de la superficie del océano, y cuando esto ocurría, las olas que creaban los árboles no permitían que ningún barco cercano se alejara y los indefensos marineros eran devorados por el Garuda.
Las nueces que se encontraban en el océano y en las playas ya no tenían cáscara, y se asemejaban a la parte inferior desmembrada de un cuerpo de mujer, incluidas las nalgas. Esta asociación se refleja en uno de los nombres botánicos arcaicos de la planta, Lodoicea callipyge Comm. ex J. St.-Hil., en el que callipyge proviene de las palabras griegas que significan «hermosa grupa». Históricamente, estas «hermosas jorobas» flotantes se recolectaban y se vendían por una fortuna en Arabia y en Europa.
En las Maldivas, cualquier nuez de coco de mer que se encontrara en el océano o en las playas debía entregarse al rey, y quedarse con una nuez para uno mismo o venderla podía acarrear la pena de muerte. Sin embargo, Rodolfo II, emperador del Sacro Imperio Romano Germánico, pudo comprar una de estas nueces por 4.000 florines de oro. El almirante holandés Wolfert Hermanssen también recibió una nuez como regalo por sus servicios, de manos del sultán de Bantam en 1602, por luchar contra los portugueses y proteger la capital de Bantam. Sin embargo, a la nuez que recibió el almirante le faltaba la parte superior; al parecer, el sultán había ordenado que se cortara la parte superior de la nuez, para no alterar la modestia del noble almirante. João de Barros creía que el coco de mer poseía sorprendentes poderes curativos, superiores incluso a los de «la piedra preciosa Bezoar». En uno de sus libros, el Dr. Berthold Carl Seemann menciona que muchos creían que las nueces eran un antídoto contra todos los venenos. Las nueces fueron alabadas no sólo por científicos y botánicos, sino también por poetas. Luís de Camões escribió:
En los solitarios islotes de Maldivia crece la planta,
bajo los mares más profundos, de poderío soberano,
cuyo pomo de cada teriaco se confiesa,
por astuta sanguijuela de antídotos los mejores
En 1769, Jean Duchemin navegó a Praslin, la segunda isla más grande de las Seychelles, en el barco L’Heureuse Marie. Se embarcó con un cargamento de estos insólitos frutos secos, que luego vendió en los mercados de la India. Después de su viaje, las nueces de coco de mer nunca volvieron a tener el mismo valor extraordinario.