Ship-based measurements of sea surface wind speed displays a spurious upward trend due to increases in anemometer height. To correct this bias, we construct a new sea surface wind dataset from ship observations of wind speed and wind wave height archived in the International Comprehensive Ocean-Atmosphere Data Set (ICOADS). The Wave and Anemometer-based Sea-surface Wind (WASWind) dataset is available at monthly resolution on a 4 degrees by 4 degrees. longitude-latitude grid from 1950 to 2011. It substantially reduces the upward trend in wind speed through height-correction for anemometer-measured winds, rejection of spurious Beaufort winds, and use of estimated winds from wind wave height. The reduced upward trend is smallest among the existing global datasets of in situ observations and comparable with those of reanalysis products. Despite the significant reduction of globally-averaged wind speed trend, WASWind features rich spatial structures in trend pattern, making it a valuable dataset for studies of climate changes on regional scales. Not only does the combination of ship winds and wind wave height successfully reproduce major modes of seasonal-to-decadal variability, but its trend patterns are also physically consistent with sea level pressure (SLP) measurements. WASWind is in close agreement with wind changes in satellite measurements by the Special Sensor Microwave Imager (SSM/I) for the recent two decades. The agreement in trend pattern with such independent observations illustrates the utility of WASWind for climate trend analysis.