The widespread use of Agent Orange (a mixture of phenoxyl herbicides) over Southern Vietnam by US Forces led to the decimation of mangrove forests in the Mekong Delta. Mangrove trees Avicennia alba were sampled across the Mekong Delta; their age was assessed using models based on internode growth and samples were genotyped for 6 microsatellite loci. The evolution of genetic diversity over time elapsed since local extinction was reconstructed and compared with the genetic diversity of an unaffected population from Thailand, The results show that genetic diversity of the A. alba population is still increasing in the Mekong Delta 3 decades after the end of the Vietnam War, but is reaching an asymptotic level that is comparable to the adjacent non-affected population of Thailand. This might be a sign of genetic recovery, but may also reveal a limitation, either of genetic enrichment due to current predominance of auto-recruitment or of demographic increase due to intraspecific competition in this pioneer species. In any case, these results, although encouraging, demonstrate that genetic recovery after complete or almost complete population depletion continues over a longer time-scale than apparent demographic recovery.