|Observations of conditions at the ocean surface have been made for centuries, contributing to some of the longest instrumental records of climate change. Most prominent is the climate data record (CDR) of sea surface temperature (SST), which is itself essential to the majority of activities in climate science and climate service provision. A much wider range of surface marine observations is available however, providing a rich source of data on past climate. We present a general error model describing the characteristics of observations used for the construction of climate records, illustrating the importance of multi-variate records with rich metadata for reducing uncertainty in CDRs. We describe the data and metadata requirements for the construction of stable, multi-century marine CDRs for variables important for describing the changing climate: SST, mean sea level pressure, air temperature, humidity, winds, clouds, and waves. Available sources of surface marine data are reviewed in the context of the error model. We outline the need for a range of complementary observations, including very high quality observations at a limited number of locations and also observations that sample more broadly but with greater uncertainty. We describe how high-resolution modern records, particularly those of high-quality, can help to improve the quality of observations throughout the historical record. We recommend the extension of internationally-coordinated data management and curation to observation types that do not have a primary focus of the construction of climate records. Also recommended is reprocessing the existing surface marine climate archive to improve and quantify data and metadata quality and homogeneity. We also recommend the expansion of observations from research vessels and high quality moorings, routine observations from ships and from data and metadata rescue. Other priorities include: field evaluation of sensors; resources for the process of establishing user requirements and determining whether requirements are being met; and research to estimate uncertainty, quantify biases and to improve methods of construction of CDRs. The requirements developed in this paper encompass specific actions involving a variety of stakeholders, including funding agencies, scientists, data managers, observing network operators, satellite agencies, and international co-ordination bodies.