Fragmentation of tropical forests is one of the major threats to biodiversity and viable natural populations. Brazilian seasonally dry tropical forests (SDTF) are endangered because of human occupation, conversion of lands to agriculture and high deforestation rates in these fertile soils. Enterolobium contortisiliquum has been removed from SDTF natural areas due to the advance of cattle grazing and agriculture in Brazilian SDTFs. To aid conservation efforts of this species we used molecular markers to study the genetic diversity and population structure of E. contortisiliquum in Brazilian SDTF remnants. A total of 263 individuals in 13 forest patches were analyzed with 103 ISSR fragments. In spite of being found scattered among the SDTF patches, E. contortisiliquum populations exhibited high genetic diversity (mean Shannon's index of diversity = 0.384; mean genetic diversity = 0.280) and genetic divergence between populations was detected (ΦST = 0.155, p < 0.0001). UPGMA dendrogram, principal coordinate analysis and Bayesian analysis showed that E. contortisiliquum populations were clustered into three groups that were not related to geographic distance (r = 0.119, p = 0.197). However, these populations are spatially structured into groups distributed in the West, Central and East of the study area. This genetic structure may be related with landscape and both the Espinhaço Range and São Francisco River may act as a partial geographic barrier limiting the gene flow. Because the highest rates of genetic diversity were found outside of conservation units, we propose the creation of protected areas in different geographic regions that include E. contortisiliquum populations from different genetic clusters.