Malaiische Seeleute hatten Coco de Mer-Nüsse gesehen, die vom Meeresboden „nach oben fielen“, und daraus geschlossen, dass diese Nüsse auf Unterwasserbäumen in einem Wald auf dem Grund des Indischen Ozeans wachsen mussten. Antonio Pigafetta und Georg Eberhard Rumphius zufolge glaubten die Malaien, dass der Baum auch die Heimat des riesigen Vogels oder vogelähnlichen Wesens Garuda (oder Rukh der Araber) sei. Afrikanische Priester glaubten, dass der Garuda in der Lage war, Elefanten und Tiger zu jagen. Die afrikanischen Priester glaubten auch, dass sich die Coco de Mer-Bäume manchmal über die Meeresoberfläche erhoben, und wenn dies geschah, erlaubten die Wellen, die die Bäume erzeugten, keinem Schiff in der Nähe, wegzufahren, und die hilflosen Seeleute wurden vom Garuda gefressen.
Die Nüsse, die man im Meer und an den Stränden fand, hatten keine Schale mehr und ähnelten dem zerstückelten Unterteil eines Frauenkörpers, einschließlich des Gesäßes. Diese Assoziation spiegelt sich in einem der archaischen botanischen Namen der Pflanze wider, Lodoicea callipyge Comm. ex J. St.-Hil., wobei callipyge aus dem Griechischen stammt und „schöner Hintern“ bedeutet. In der Vergangenheit wurden diese schwimmenden „schönen Höcker“ gesammelt und in Arabien und Europa für ein Vermögen verkauft.
Auf den Malediven sollten alle Coco de Mer-Nüsse, die im Meer oder an den Stränden gefunden wurden, dem König geschenkt werden, und der Besitz einer Nuss für sich selbst oder ihr Verkauf hätte die Todesstrafe zur Folge gehabt. Rudolf II., Kaiser des Heiligen Römischen Reiches, konnte jedoch eine dieser Nüsse für 4.000 Goldgulden erwerben. Auch der niederländische Admiral Wolfert Hermanssen erhielt 1602 vom Sultan von Bantam eine Nuss als Geschenk für seine Dienste im Kampf gegen die Portugiesen und zum Schutz der Hauptstadt von Bantam. Bei der Nuss, die dem Admiral überreicht wurde, fehlte jedoch der obere Teil; offenbar hatte der Sultan angeordnet, den oberen Teil der Nuss abzuschneiden, um die Bescheidenheit des Admirals nicht zu verletzen. João de Barros glaubte, dass Coco de Mer erstaunliche Heilkräfte besaß, die sogar denen des „Edelsteines Bezoar“ überlegen waren. Dr. Berthold Carl Seemann erwähnte in einem seiner Bücher, dass viele glaubten, die Nüsse seien ein Gegengift für alle Gifte. Die Nüsse wurden nicht nur von Wissenschaftlern und Botanikern, sondern auch von Dichtern gepriesen. Luís de Camões schrieb:
Auf den einsamen Inseln Malediviens wächst die Pflanze,
unter den tiefsten Meeren, von souveräner Macht,
deren Kern jeder Theriack bekannt ist,
durch schlauen Blutegel von Gegenmitteln das beste
Im Jahr 1769 segelte Jean Duchemin mit dem Schiff L’Heureuse Marie nach Praslin, der zweitgrößten Insel der Seychellen. Er hatte eine Ladung dieser ungewöhnlichen Nüsse an Bord, die er später auf indischen Märkten verkaufte. Nach seiner Reise hatten die Coco de Mer-Nüsse nie wieder denselben außergewöhnlichen Wert.