Camellia nitidissima, a rare plant but a useful genetic resource for commercial cultivation of ornamental camellias, is distributed in a narrow region of South China and North Vietnam. In this study, RAPD and AFLP markers were used to assess the genetic diversity and population structure of six natural populations of C. nitidissima from Guangxi in South China. Twenty RAPD primers amplified 183 bands, of which 143 bands were polymorphic, and 8 AFLP primer pairs produced 502 bands, of which 364 were polymorphic. Independent as well as combined analyses of the cluster analyses of the RAPD and AFLP fragments showed that the six populations could be classified into two major genetic groups corresponding to the Nanning and Fangcheng areas. The Mantel test revealed significant correlation between the genetic and geographic distances of C. nitidissima populations (r = 0.953, p = 0.036). AMOVA analysis allowed the partitioning of the genetic variation between groups (36.09%), among populations within groups (25.78%), and within populations (38.14%). An understanding of both the genetic diversity and the population structure of C. nitidissima in China can also provide insight into the conservation and management of this endangered species.