In many regions of the world, the extremes of winter cold are a major determinant of the geographic distribution of perennial plant species and of their successful cultivation. In the United States, the U.S. Department of Agriculture (USDA) Plant Hardiness Zone Map (PHZM) is the primary reference for defining geospatial patterns of extreme winter cold for the horticulture and nursery industries, home gardeners, agrometeorologists, and plant scientists. This paper describes the approaches followed for updating the USDA PHZM, the last version of which was published in 1990. The new PHZM depicts 1976–2005 mean annual extreme minimum temperature, in 2.8°C (5°F) half zones, for the conterminous United States, Alaska, Hawaii, and Puerto Rico. Station data were interpolated to a grid with the Parameter-Elevation Regressions on Independent Slopes Model (PRISM) climate-mapping system. PRISM accounts for the effects of elevation, terrain-induced airmass blockage, coastal effects, temperature inversions, and cold-air pooling on extreme minimum temperature patterns. Climatologically aided interpolation was applied, based on the 1971–2000 mean minimum temperature of the coldest month as the predictor grid. Evaluation of a standard-deviation map and two 15-yr maps (1976–90 and 1991–2005 averaging periods) revealed substantial vertical and horizontal gradients in trend and variability, especially in complex terrain. The new PHZM is generally warmer by one 2.8°C (5°F) half zone than the previous PHZM throughout much of the United States, as a result of a more recent averaging period. Nonetheless, a more sophisticated interpolation technique, greater physiographic detail, and more comprehensive station data were the main causes of zonal changes in complex terrain, especially in the western United States. The updated PHZM can be accessed online (http://www.planthardiness.ars.usda.gov).