In this study, the variability and trends of the outdoor thermal discomfort index (DI) in the Kingdom of Saudi Arabia (KSA) were analyzed over the 39-year period of 1980–2018. The hourly DI was estimated based on air temperature and relative humidity data obtained from the next-generation global reanalysis from the European Center for Medium-Range Weather Forecasts and in-house high-resolution regional reanalysis generated using an assimilative Weather Research Forecast (WRF) model. The DI exceeds 28°C, i.e., the threshold for human discomfort, in all summer months (June–September) over most parts of the KSA due to a combination of consistently high temperatures and relative humidity. The DI is greater than 28°C for 8–16 hours over the western parts of KSA and north of the central Red Sea. A DI of > 28°C persistes for 7–9 hours over the Red Sea and western KSA for 90% of summer days. The spatial extent and number of days with DI > 30°C, i.e., the threshold for severe human discomfort, are significantly lower than those with DI > 28°C. Long-term trends in the number of days with DI > 28°C indicate a reduced rate of increase or even a decrease over some parts of the southwestern KSA in recent decades (1999–2018). Areas with DI > 30°C, in particular the northwestern regions of the Arabian Gulf and its adjoining regions, also showed improved comfort levels during recent decades. Significant increases in population and urbanization have been reported throughout the KSA during the study period. Analysis of five-years clinical data suggests a positive correlation between higher temperatures and humidity with heat-related deaths during the Hajj pilgrimage. The information provided herein is expected to aid national authorities and policymakers in developing necessary strategies to mitigate the exposure of humans to high levels of thermal discomfort in the KSA.