Under the efficient market hypothesis (EMH), part of the literature ignores the characteristics of carbon markets. Based on the fractal market hypothesis (FMH), using the MF-DCCA method, this empirical study complements related research. We studied the non-linear multifractal correlation between carbon price fluctuations and China’s economic policy uncertainty (CNEPU) in Shenzhen, Beijing, Tianjin, and the national carbon market. The results show the following: (1) There is no linear correlation between price volatility and CNEPU in all carbon markets. (2) In the national carbon market, the correlation linkage between price fluctuation and CNEPU has not yet formed. (3) In the three regional carbon markets of Shenzhen, Beijing, and Tianjin, the long-range correlations exist with anti-persistence multifractal characteristics, which means that an increase in CNEPU will reduce price fluctuations. (4) After dividing the time scale into long-term and short-term, we found that it does not change the multifractal characteristics but it does change the fractal intensity. Finally, some suggestions are given to policymakers and carbon finance investors.