Nan Madol est le siège cérémoniel et politique de la dynastie « Sau-Deleur » ("seigneur de Deleur" en pohnpeien, « Deleur » étant l'ancien nom de l'île), qui unifia la population de Pohnpei (estimée à 25 000 personnes[1]). Selon les traditions orales, la dynastie des Saudeleur, arrivés sur de grands bateaux, était originaire de Katau (ou Kanamwayso), îles situées à l'ouest, et soumit la population autochtone. La légende fait débuter la dynastie, et la construction de la cité, par l'arrivée des deux sorciers jumeaux : Olisihpa et Olosohpa, capables de faire léviter les sections d'orgues basaltiques utilisées dans beaucoup d'endroits de Nan Madol, depuis leur lieu d'extraction jusqu'au site de construction, grâce au concours d'un dragon volant et sous les auspices de Nahnisohn Sahpou, dieu de l'agriculture. Après plusieurs essais infructueux, ils réussirent et commencèrent la construction par l'autel de Nahnisohn Sahpou. Quand Olisihpa mourut de vieillesse, Olosohpa devint le premier « seigneur de Deleur », épousa une autochtone et fonda ainsi le clan Dipwilap (« Grand ») qui gouverna la cité et l'île. Ces traditions se retrouvent avec de nombreuses variantes dans la plupart des îles de l'océan Pacifique, c'est le cas par exemple de la légende polynésienne d'Hawaiki[2]. Sachant que le peuplement de l'Océanie s'est fait depuis l'ouest, d'île en île, les ethnologues interprètent Katau/Kanamwayso comme Chuuk, voire les Philippines ou même Fou-nan dans l'Indochine (de plus, à Lelu dans Kosrae il existe un autre complexe mégalithique semblable)[3].

Quoi qu'il en soit, les recherches archéologiques montrent que Nan Madol fut le lieu d'une activité humaine dès le premier ou le IIe siècle de notre ère. Au VIIIe siècle ou IXe siècle, les constructions sur les îlots commencent, mais l'architecture mégalithique n'a probablement pas commencé avant le XIIe siècle ou le début du XIIIe siècle. De la tradition orale, peu de choses peuvent être vérifiées sur la construction des mégalithes. Les architectes, eux, pensent que les orgues basaltiques ont été transportées par voie de terre roulées sur des troncs de cocotiers et par voie d'eau sur des flotteurs en profitant des marées hautes dans les canaux de la mangrove[4].