We investigated 29 natural populations of Cryptomeria japonica using 148 cleaved amplified polymorphic sequence markers to elucidate their genetic structure and identify candidate adaptive genes of this species. In accordance with the inferred evolutionary history of the species during and after the last glacial episode, the genetic diversity was higher in western populations than in northern populations. The results of phylogenetic and genetic structure analyses suggest that populations of the two main varieties of the species have clearly diverged from each other and that two of the examined loci are strongly associated with the differentiation between the two varieties. Using a coalescent simulation based on F(ST) and H(e) values, we detected five genes that had higher, and two that had lower, values than the respective 99% confidence intervals (C.I.s) that are theoretically expected intervals under a neutral infinite-island model. We also detected 13 outlier loci using a coalescent simulation based on the assumption that the 2 varieties originated from the splitting of an ancestral population. Four of these loci were detected by both methods, two of which were detected in a genetic structure analysis as loci associated with differentiation between the two varieties of the species, and are strong candidates for genes that have been subject to selection.