Air humidity in the near-surface atmospheric layer over the ocean is a key parameter influencing the transfer of moisture and heat between the ocean and atmosphere, as well as the dynamics of atmospheric processes as a whole. Analysis of meteorological data collected during the 20th century reveals significant spatial and temporal sparsity in humidity measurements. The International Comprehensive Ocean–Atmosphere Data Set (ICOADS) indicates that the density of observations in the early 20th century was considerably lower compared to later periods, which complicates adequate analysis of long-term relative humidity trends. Methods for reconstructing humidity time series presented in the literature often demonstrate limited accuracy, relying primarily on statistical and heuristic approaches. Our study aims to improve the quality of such reconstructions by applying machine learning methods. In this work, the problem is formulated as the approximation of instantaneous relative humidity values based on auxiliary measurements of atmospheric pressure, air temperature, wind speed and direction, sea surface temperature, and observations of cloud amount and type at three levels. Additional predictors include the WMO weather code and the calculated solar elevation angle. The machine learning models explored include linear regression, decision tree, random forest, gradient boosting, and a fully connected artificial neural network. To enhance the spatial and seasonal specificity of the developed models, the analysis was performed separately for each 2° latitude–longitude grid cell (geographical trapezoid) and for each season. Based on the results, maps of the spatial distribution of model errors were produced, enabling the identification of regions with high and low approximation accuracy. The study confirms the effectiveness of machine learning methods for reconstructing climate time series, identifies the most suitable models for this task, and outlines promising directions for further research.