Early seedling establishment and seedling vigor are essential components of crop development and eventual yield in sorghum (Sorghum bicolor (L.) Moench). However, suboptimal temperatures in the early season often limit stand establishment. Genetic variation for early-season cold tolerance has been observed in sorghum. This study was undertaken to assess the extent of genetic variation, to estimate heritability of seedling cold tolerance, and to determine correlations between seedling traits and associated agronomic traits under cold stress and non-stress environments. A set of 528 recombinant inbred lines (RILs) developed from a cross between two contrasting parents: SRN39 (African Caudatum) and Shan Qui Red (SQR) (Chinese Kaoliang), were evaluated for seedling vigor and related agronomic traits under early-season (cold) and later (optimal) plantings over two years. Parental lines were included as checks. The kaoliang parent was constantly superior in seedling vigor under both plantings. We observed large genetic variation and high transgressive segregation among the RILs for seedling vigor traits under both growing conditions. Heritability estimates were high for all seedling traits measured, and were similar between planting dates. This may suggest that seedling vigor and early season cold tolerance in the SQR parent may be under the same genetic control. Seedling vigor scores, based on visual appearance of the seedlings, were taken at three different times throughout the early season. These scores showed moderate correlation with seedling biomass and strong correlation with seedling height, demonstrating the utility of visual scores for assessing seedling performance in large trials.