Changes in genetic variability and allele frequency can be responses from natural populations when encountering a novel contaminated environment. The genetic diversity and population structuring of natural populations of the gastropod Littorina brevicula from heavy-metal polluted and unpolluted environments along the southeast coast of Korea were examined using two mtDNA markers, cyt b and ND6. This study applied a nested clade analysis to test the existence of structuring association of haplotype distribution with environments (polluted and unpolluted). No genetic differences within cyt b mtDNA were detected between environments. On the other hand, differences in population haplotype diversity and structuring were found within ND6 mtDNA between polluted and unpolluted environments. The ND6-mtDNA haplotype (=genetic) diversity was significant lower in polluted environments. This decreased genetic diversity along with differences in the haplotype distribution within heavy-metal polluted environments compared to those unpolluted ones stand out as emergent effects from pollution at a population level. In this study, we propose the use of different approaches, such as the NCA, that takes into account the rare haplotypes, when assessing the effects of pollution on population genetic structuring.