As an important parameter to characterize physical and biogeochemical processes, sea surface salinity (SSS) has received extensive attention. Cubist is a data mining model, which can be well-suited to estimate and analyze SSS in the Gulf of Mexico (GOM) because it can reflect the SSS internal heterogeneity in the GOM—overall circular distribution, and the seasonality related to temperature and river discharge changes. Using remote sensing reflectance (Rrs) at 412, 443, 488 (490), 555, and 667 (670) nm and sea surface temperature (SST), a cubist model was developed to estimate SSS with high accuracy with the overall performance demonstrates a root mean square error (RMSE) of 0.27 psu and correlation coefficient of 0.97 of R2. The model divides the GOM area according to model rules into four sub-regions, which include estuary, nearshore, and open sea, reflecting the gradient distribution of SSS. The division of sub-regions and seasonal changes can be explained by the distribution of water bodies, river discharges, and local wind forces since it is obvious that the estuary region reaches the largest low-value area and spreads eastward with the monsoon in the spring when the river flow increases to the highest value. While the east to west wind in the non-summer monsoon period guides the plume westward, and the lowest river discharge in winter corresponds to the smallest low value area. After comparison with other statistical models, the cubist model showed satisfactory results in independent verification of cruise data, proving the estimation capability under different geographical conditions (such as estuaries and open seas) and seasons. Therefore, considering high accuracy and heterogeneity mining, the cubist-based model is an ideal method for coastal SSS estimation and spatial-temporal heterogeneity analysis, and can provide ideas for model construction for coastal areas with similar geographic environments.