Inference of genetic structure and demographic history is fundamental issue in evolutionary biology. We examined the levels and patterns of genetic variation of a widespread mangrove species in the Indo-West Pacific region, Bruguiera gymnorrhiza, using ten nuclear gene regions. Genetic variation of individual populations covering its distribution range was low, but as the entire species it was comparable to other plant species. Genetic differentiation among the investigated populations was high. They could be divided into two genetic clusters: the West and East clusters of the Malay Peninsula. Our results indicated that these two genetic clusters derived from their ancestral population whose effective size of which was much larger compared to the two extant clusters. The point estimate of speciation time between B. gymnorrhiza and Bruguiera sexangula was two times older than that of divergence time between the two clusters. Migration from the West cluster to the East cluster was much higher than the opposite direction but both estimated migration rates were low. The past Sundaland and/or the present Malay Peninsula are likely to prevent gene flow between the West and East clusters and function as a geographical or land barrier.