We assess our confidence in the historical marine surface temperature record as provided by the International Comprehensive Ocean-Atmosphere Data Set (ICOADS). New flexible analyses of sea surface temperature (SST) and night-time marine air temperature (NMAT) since the 1850s are presented and their uncertainties quantified. Owing to the expanded ICOADS data base, these analyses are superior in geographical coverage to previous analyses. We introduce the issues involved in analysing a data base of observations made from diverse platforms by many different countries with different measurement practices. Bias corrections are applied to the data to account for changes in measurement conditions through time and an analysis of uncertainties in these corrections is included. A first-order assessment of total uncertainty in each gridded average is obtained by combining these bias correction related uncertainties with those arising from measurement errors and under-sampling of intra-grid box variability. From month to month in individual grid boxes, sampling uncertainties tend to be most important, but for large scale averages after around 1900, they are negligible (for SST) or comparable (for NMAT) to bias correction uncertainties. We assess the impact of these uncertainties on our estimates of long-term trends.