The Natuna Islands were the foremost islands of Indonesia as an important landmark on the navigation routes within the South China Sea. Historically, the Natuna Islands had an important role on the maritime trade routes linking the Eastern and Western worlds, especially between 10th-14th centuries CE. Many ships were lost on the journey to the Natunas because of submerged rocks, reefs, bad weather and the dynamic conditions of the sea. Remains of underwater cultural heritage sites, such as ancient shipwrecks and their cargo, can be found at various locations on the seabed and around the coast of Natunas. They have high historical value. Unfortunately, research and recent surveys show that many threats are destabilizing the sites and their ecosystems due mostly to geodynamic conditions, illegal excavation of the site, treasure hunters and fishing trawlers. In consequence, the development of a marine eco-archaeological park was proposed for preserving underwater cultural heritage sites in Natunas, as well as developing site attractions for marine tourism. This paper offers a case study that examines characteristics of underwater cultural heritage sites in support of a marine eco-archaeological park in the Natuna Islands waters. The methods used in this study were multidisciplinary, such as geology and geophysical analysis for the distribution of surface sediment of the sites, marine ecology for analysing ecosystem conditions around the sites and maritime archaeology for site assessment. The data was combined and analysed using a submerged cultural resources approach for adopting the marine eco-archaeological park model. The results show three locations of underwater cultural heritage sites in the Natuna Islands with different characteristics that are represented by an assessment score. The three locations are the Tanjung Senubing shipwreck site, the Buton shipwrecks site and the Djadayat shipwreck site. The Djadayat shipwreck site has the greatest potential for being developed as a marine eco-archaeological park in the Natuna Islands.