Cold temperature is an important abiotic stress affecting sorghum production in temperate regions. It reduces seed germination, seedling emergence and seedling vigor thus limiting the production of the crop both temporally and spatially. The objectives of this study were (1) to assess early season cold temperature stress response of sorghum germplasm from cooler environments and identify sources of tolerance for use in breeding programs, (2) to determine population structure and marker-trait association among these germplasms for eventual development of marker tools for improving cold tolerance. A total of 136 sorghum accessions from cooler regions of the world were phenotyped for seedling growth characteristics under cold temperature imposed through early planting. The accessions were genotyped using 67 simple sequence repeats markers spanning all ten linkage groups of sorghum, of which 50 highly polymorphic markers were used in the analysis. Genetic diversity and population structure analyses sorted the population into four subpopulations. Several accessions distributed in all subpopulations showed either better or comparable level of tolerance to the standard cold tolerance source, Shan qui red. Association analysis between the markers and seedling traits identified markers Xtxp34, Xtxp88, and Xtxp319 as associated with seedling emergence, Xtxp211 and Xtxp304 with seedling dry weight, and Xtxp20 with seedling height. The markers were detected on chromosomes previously found to harbor QTLs associated with cold tolerance in sorghum. Once validated these may serve as genomic tools in marker-assisted breeding or for screening larger pool of genotypes to identify additional sources of cold tolerance.