Contemporary mangrove forest areas took shape historically and their genetic connectivity depends on sea-faring propagules, subsequent settlement, and persistence in suitable environments. Mangrove species world-wide may experience genetic breaks caused by major land barriers or opposing ocean currents influencing their population genetic structure. For Malay Peninsula, several aquatic species showed strong genetic differentiation between East and West coast regions due to the Sunda shelf flooding since the Last Glacial Maximum. In this study genetic diversity and structure of Avicennia marina populations in Malay Peninsula were assessed using nuclear microsatellite markers and chloroplast sequences. Even though all populations showed identical morphological features of A. marina, three evolutionary significant units were obtained with nuclear and cytoplasmic markers. Avicennia marina along a 586 km stretch of the West coast differed strongly from populations along an 80 km stretch of the East coast featuring chloroplast capture of Avicennia alba in an introgressive A. marina. Over and above this expected East-West division, an intra-regional subdivision was detected among A. marina populations in the narrowest region of the Strait of Malacca. The latter genetic break was supported by an AMOVA, STRUCTURE, and BARRIER analysis whereas R_ST > F_ST indicated an evolutionary signal of long-lasting divergence. Two different haplotypes along the Western coast showed phylogeographic relationship with either a northern or a putative southern lineage, thereby assuming two Avicennia sources facing each other during Holocene occupation with prolonged separation in the Strait of Malacca. MIGRATE-n model testing supported a northward unidirectional stepping-stone migration route, although with an unclear directionality at the genetic break position, most likely due to weak oceanic currents. Low levels of genetic diversity and southward connectivity was detected for East coast Avicennia populations. We compared the fine-scale spatial genetic structure (FSGS) of Avicennia populations along the exposed coast in the East vs. the sheltered coast in the West. A majority of transects from both coastlines revealed no within-site kinship-based FSGS, although the remoteness of the open sea is important for Avicennia patches to maintain a neighborhood. The results provide new insights for mangrove researchers and managers for future in-depth ecological-genetic-based species conservation efforts in Malay Peninsula.