While rhizome formation is intimately associated with perennialism and the derived benefit of sustainability, the introduction of this trait into temperate-zone adapted Sorghum cultivars requires precise knowledge of the genetics conditioning this trait in order to minimize the risk of weediness (e.g., Johnsongrass, S. halepense) while maximizing the productivity of perennial sorghum. As an incremental step towards dissecting the genetics of perennialism, a segregating F4 heterogeneous inbred family derived from a cross between S. bicolor and S. propinquum was phenotyped in both field and greenhouse environments for traits related to over-wintering and rhizome formation. An unseasonably cold winter in 2011 provided high selection pressure, and hence 74.8 % of the population did not survive. This severe selection pressure for cold tolerance allowed the resolution of two previously unidentified over-wintering quantitative trait locus (QTL) and more powerful correlation models than previously reported. Conflicting with previous reports, a maximum of 33 % of over-wintering variation could be explained by above-ground shoot formation from rhizomes; however, every over-wintering plant exhibited rhizome growth. Thus, while rhizome formation is required for over-wintering, other factors also determine survival in this interspecific population. The fine mapping of a previously reported rhizome QTL on sorghum chromosome SBI-01 was conducted by targeting this genomic region with additional simple sequence repeat markers. Fine mapping reduced the 2-LOD rhizome QTL interval from ~59 to ~14.5 Mb, which represents a 75 % reduction in physical distance and a 53 % reduction in the number of putative genes in the locus. ELECTRONIC SUPPLEMENTARY MATERIAL: The online version of this article (doi:10.1007/s11032-012-9778-8) contains supplementary material, which is available to authorized users.