Sandy coastal plant communities in tropical regions have been historically under strong anthropic pressure. In Brazil, these systems shelter communities with highly plastic plant species. However, the potential of these systems to regenerate without human assistance after disturbances has hardly been examined. We determined the natural regeneration of a coastal sandy plain vegetation (restinga) in Brazil, 16 years after the end of sand removal. We inventoried 38 plots: 20 within a sand-mined site and 18 in an adjacent undisturbed site. We expected lower diversity values in the sand-mined site compared to the undisturbed site, but similar species composition between the two sites due to the spatial proximity of the two sites and the high plasticity of restinga species. Species were ranked using abundance and importance value index in both sites, and comparisons were performed using Rényi entropy profiles, rarefaction curves, principal component analysis, and redundancy analysis. Species composition and dominant species differed markedly between the two sites. Bromeliads and Clusia hilariana, well-known nurse plants, dominated the undisturbed site but were almost absent in the regenerating site. Species richness did not differ between both sites, but diversity was higher in the undisturbed site. Within-site composition differences in the mined area were associated with field characteristics. Interestingly, species classified as subordinate or rare in the undisturbed site became dominants in the regenerating site. These newer dominants in the sand-mined site are not those known as nurse plants in other restingas, thus yielding strong implications for restoration.