Low temperature affects the rice plants at all stages of growth. It can cause severe seedling injury and male sterility resulting in severe yield losses. Using a mini core collection of 174 Chinese rice accessions and 273 SSR markers we investigated cold tolerance at the germination and booting stages, as well as the underlying genetic bases, by association mapping. Two distinct populations, corresponding to subspecies indica and japonica showed evident differences in cold tolerance and its genetic basis. Both subspecies were sensitive to cold stress at both growth stages. However, japonica was more tolerant than indica at all stages as measured by seedling survival and seed setting. There was a low correlation in cold tolerance between the germination and booting stages. Fifty one quantitative trait loci (QTLs) for cold tolerance were dispersed across all 12 chromosomes; 22 detected at the germination stage and 33 at the booting stage. Eight QTLs were identified by at least two of four measures. About 46% of the QTLs represented new loci. The only QTL shared between indica and japonica for the same measure was qLTSSvR6-2 for SSvR. This implied a complicated mechanism of old tolerance between the two subspecies. According to the relative genotypic effect (RGE) of each genotype for each QTL, we detected 18 positive genotypes and 21 negative genotypes in indica, and 19 positive genotypes and 24 negative genotypes in japonica. In general, the negative effects were much stronger than the positive effects in both subspecies. Markers for QTL with positive effects in one subspecies were shown to be effective for selection of cold tolerance in that subspecies, but not in the other subspecies. QTL with strong negative effects on cold tolerance should be avoided during MAS breeding so as to not cancel the effect of favorable QTL at other loci.