Soil salinization will affect 50% of global cropland areas by 2050 and represents a major threat to agricultural production and food sovereignty. As soil salinity monitoring is costly and time consuming, many regions of the world undertake very limited soil salinity observation (in space and time), preventing the accurate assessment of soil salinity hazards. In this context, this study assesses the relative performance of Sentinel-1 radar and Sentinel-2 optical images, and the combination of the two, for monitoring changes in soil salinity at high spatial and temporal resolution, which is essential to evaluate the mitigation measures required for the sustainable adaptation of agriculture practices. For this purpose, an improved learning database made of 863 soil electrical conductivity (i.e., soil salinity) observations is considered for the training/validation step of a Random Forest (RF) model. The RF model is successively trained with (1) only Sentinel-1, (2) only Sentinel-2 and (3) both Sentinel-1 and -2 features using the Genetic Algorithm (GA) to reduce multi-collinearity in the independent variables. Using k-fold cross validation (3-fold), overall accuracy (OA) values of 0.83, 0.88 and 0.95 are obtained when considering only Sentinel-2, only Sentinel-1 and both Sentinel-1 and -2 features as independent variables. Therefore, these results highlight the clear complementarity of radar (i.e., Sentinel-1) and optical (i.e., Sentinel-2) images to improve soil salinity mapping, with OA increases of approximately 10% and 7% when compared to Sentinel-2 and Sentinel-1 alone. Finally, pre-sowing soil salinity maps over a five-year period (2019–2023) are presented to highlight the benefit of the proposed procedure to support the sustainable management of agricultural lands in the context of soil salinization on a regional scale.