Budowa wysepek najprawdopodobniej została rozpoczęta ok. 1200 roku, istniejące już wysepki rozbudowano i wzniesiono nowe z ułożonych jeden na drugim bloków bazaltowych wydobytych w innej części Pohnpei i przetransportowanych do budowy Nan Madol bez użycia kół czy narzędzi metalowych. Według legendy Nan Madol zostało wzniesione przez dwóch braci przy użyciu nadprzyrodzonych mocy.
Nan Madol było zamieszkane, ale jego populacja nie przekraczała 1000 osób. Szacuje się, że mieszkańców mogło być mniej niż 500.
Na wysepkach w północno-wschodniej części Nan Madol – Madol Powe – mieszkali kapłani. Inne wysepki służyły konkretnym celom – na jednych przygotowywano pożywienie (np. na Usennamw) a na innych budowano kanu (np. na Dapahu) czy produkowano olej kokosowy (np. na Peinering). Nandauwas pełniło funkcję królewskiego domu pogrzebowego. 34 wysepki tworzyły centrum administracyjne, znajdowały się tu również domy mieszkalne arystokracji. Rezydencje saudeleura i jego rodziny stały na wysepce Pahnkadira. Na wysepce Idehd trzymany był święty węgorz, którego karmiono wnętrznościami żółwi. Drugi święty węgorz miał być trzymany na wysepce Dorong, gdzie hodowano małże.