Barium addition to chromite ore processing residue (COPR) was investigated in order to address (a) the pronounced heaving phenomena that are associated with mainly the presence of ettringite and (b) hexavalent chromium leaching. Sulfate was added to representative samples of grey-black (GB) and hard-brown (HB) COPR to simulate worst-case conditions of sulfate influx and ettringite formation. Both the X-ray powder diffraction (XRPD) and the modeling results showed that ettringite is a thermodynamically favored reaction in COPR. The subsequent addition of barium lead to the formation of both barite and barium chromate, observed as solid solution between the two phases. Modeling results confirmed that barium sulfate is the more stable species that will dissolve ettringite and that barium chromate will also dissolve COPR chromate phases when sulfate is depleted. The Toxicity Characteristic Leaching Procedure (TCLP) test on GB samples showed that the optimal stoichiometry to maintain Cr and Ba TCLP concentrations below the U.S. Environmental Protection Agency regulatory limit of 5 and 100 ppm, respectively, lies between 1:1 (Ba to sulfate plus chromate ratio) and 1.5:1. The respective optimal stoichiometry for the HB COPR was found to be higher, between 2:1 and 5:1. Considering that COPR is actually a Cr-contaminated cement form, a further area of research is the identification of barium-containing wastes (i.e., heavy-metal sludges, contaminated soils, etc.) that would be suitable for combination with COPR; in this way, an environmentally sustainable yet cost-effective treatment application can be realized.