The catalytic effect of red mud on Vietnam anthracite’s combustion characteristics was investigated. The mineralogical composition of the red mud includes CaCO3, Fe2O3, FeO(OH), FeTiO3, and Al(OH)3. This red mud is rich in Na, Ca, Al, Fe, and Ti. The combustion characteristics were analyzed by the thermogravimetry method. The combustion effectiveness was assessed by thermogravimetric analysis. The results were derived from a combination of several parameters, such as the ignition temperature, the burnout efficiency, and the amount of heat release. The combustion characteristics of pulverized coal were improved by the introduction of red mud, and the greatest catalytic performance was achieved when the content reached 6%. With the optimal addition, the ignition temperature of anthracite was reduced by 12 °C, and the burnout efficiencies were increased by 2.59% compared to raw anthracite. The amount of heat released by anthracite was increased to 6.93 kJ/g by adding red mud.