Both economic policy uncertainty (EPU) innovation and investor sentiment affect stock market returns. However, their relative importance is typically examined separately in the finance literature. This study concentrates on examining how different investor sentiment regimes affect the relationship of EPU innovation and future stock market returns. Using the Baker et al. (2016) news-based measure to capture the changes in EPU in the United States and an indirect market-based index (Baker and Wurgler, 2006) as a proxy for different sentiment regimes, we find that EPU innovation is negatively correlated with future stock market returns. The negative predictive ability of changes in EPU on future stock returns is only significant under a high-sentiment regime. After adding the lagged business cycle and market volatility variables, the negative predictive ability of changes in EPU on future stock returns is still better under a high-sentiment regime than the negative predictive ability under a low-sentiment regime.