A mesterséges szigetek többsége a 13. és 17. század között épült. Mindegyik sziget más célt szolgált. Némelyiken laktak, más szigetek például kenukészítésre vagy szertartásos táncokra voltak fenntartva. Mindegyiket különböző formájúra és méretűre építették, nincs két egyforma sziget.

Nan Madol épületeinek megépítéséhez több ezer faragatlan oszlopot kellett ideszállítani. Van egy olyan alapkő, aminek a súlyát 50 tonnára becsülik. Nem lehet tudni, hogyan szállították ide a hatalmas kőtömböket, mert egy egyszerű tutaj nem bírná el ezeket, a legközelebbi bazaltlelőhely pedig több kilométerre található.

Rejtélye nyomán rengeteg legenda, mendemonda, felvetés született, mert nem tudni, kik és hogyan építették. Az egyik szerint sok-sok évszázaddal ezelőtt két testvér olyan varázserőt kapott az istenektől, amellyel képesek voltak a nehéz köveket elrepíteni az építkezési területre. Mások szerint Pohnpein valamikor fejlett civilizáció élt, akik ismerték a hanghullámok irányításának titkát, így voltak képesek mozgatni és helyére emelni a hatalmas kődarabokat. A legelfogadottabb feltevés az, hogy az elhagyatott város rengeteg ember munkájának eredménye és nagyon sok évig épült.

Nan Madol mintegy 1000 embernek adott otthont, és már 200 éve lakatlanul áll. Azt sem lehet tudni pontosan, hogy miért hagyhatták el a lakói, ezért erre is sok felvetés született. Egyesek szerint egy betegség tizedelte meg a lakosságot, ezért a túlélők más otthont kerestek. Mások szerint egy tájfun következtében megsemmisült a lakók élelmiszerkészlete, ezért álltak tovább.

Az első idegenek, akik rábukkantak Nan Madolra, valószínűleg európai felfedezők voltak az 1800-as években. A város érkezésük előtt körülbelül 100 évvel válhatott elhagyatottá, vagyis lakói valamikor az 1700-as években távoztak.