To investigate the evolution of clinal variation in an invasive plant, we compared cold hardiness in the introduced saltcedar (Tamarix ramosissima, Tamarix chinensis, and hybrids) and the native plains cottonwood (Populus deltoidessubsp. monilifera). In a shadehouse in Colorado (41°N), we grew plants collected along a latitudinal gradient in the central United States (29–48°N). On 17 occasions between September 2005 and June 2006, we determined killing temperatures using freeze-induced electrolyte leakage and direct observation. In midwinter, cottonwood survived cooling to −70°C, while saltcedar was killed at −33 to −47°C. Frost sensitivity, therefore, may limit northward expansion of saltcedar in North America. Both species demonstrated inherited latitudinal variation in cold hardiness. For example, from September through January killing temperatures for saltcedar from 29.18°N were 5–21°C higher than those for saltcedar from 47.60°N, and on September 26 and October 11, killing temperatures for cottonwood from 33.06°N were >43°C higher than those for cottonwood from 47.60°N. Analysis of nine microsatellite loci showed that southern saltcedars are more closely related to T. chinensis while northern plants are more closely related to T. ramosissima. Hybridization may have introduced the genetic variability necessary for rapid evolution of the cline in saltcedar cold hardiness.