Casuarina equisetifolia is an important tree species in tropical/subtropical zones of Asia, the Pacific and Africa. In this study, 220 individuals from seven native provenances and eleven introduced provenances of C. equisetifolia were analyzed to assess the genetic variation and structure using amplified fragment length polymorphism (AFLP) markers. A total of 465 bands were obtained by eight primer pairs, among which 153 were polymorphic. The mean NEI’s gene diversity H = 0.2113 calculated for 18 provenances and the total gene diversity HT = 0.4065 calculated for native provenances suggested abundant variation within provenances and species. High genetic divergence coefficient (GST = 0.4737) and low gene flow (Nm = 0.5555) detected among native provenances suggesting high differentiation of C. equisetifolia. An AMOVA analysis for native provenances revealed a high proportion (46.07%) of the total genetic variation distributed among provenances. The UPGMA clustering (r = 0.8028) and the Mantel test (r = 0.0716) for native provenances showed there was no correlation among genetic relationships and geographical distribution. The genetic information provided important implications for the future conservation and breeding programs of C. equisetifolia.