In the hyper-arid Namib Desert, fog serves as the only regular source of moisture, vital for sustaining local ecosystems. While fog occurrence in the region is typically associated with the advection of marine stratus clouds and their interaction with topography, its spatial distribution is strongly influenced by cloud base height, which remains poorly understood. To address this gap, this study utilizes ground-based remote sensing and in-situ observations to analyze systematic spatial and temporal patterns of cloud base height. Our results reveal clear seasonality and a diurnal cycle, with cloud base lowering moderately (10-50 m h-1 ) during the evening and early night, and lifting rapidly (30-150 m h-1 ) after sunrise, especially inland. A strong and consistent negative correlation (r ≈ -0.75) between cloud base height and near-surface relative humidity was identified using quantile regression, enabling accurate cloud base height estimation with a mean absolute error of 46 m and a mean absolute percentage error of 19 % relative to ground-based measurements. In a case study, the potential value of the estimated cloud base height for separating fog from low clouds in satellite-based products is shown. In the future, a full integration of the estimated cloud base height with a satellite-based fog and low-cloud product can enable a spatially continuous mapping of fog in the region for the first time, which would facilitate fog ecological impact studies.