First-principles calculations were performed to study the phase stability of M23C6, (M = V, Cr, Mn, Fe, Co, Ni) and the solubility of d-impurities (Fe, Co, Ni, W) in Cr23C6, which is the most prevalent carbide in chromium steels. Our results correctly predict the relative stability of binary carbides, among which the most stable compounds are V23C6, Cr23C6 and Mn23C6. Stability of the M23C6 and MC carbides was related to the Md-filling, where the M-M and M-C bonds provide the cohesive properties, respectively. We demonstrated that iron and nickel should always be present in Cr23C6, where their concentrations may reach 50 at.% and 30 at.%, respectively. To predict the ways to control the carbide stabilization and distribution in iron matrix, both of which govern the microstructure and mechanical properties of high-alloy steels, we also investigated the effect of tungsten addition on the stability of quaternary carbides, namely (Cr, W, M)23C6 (M = Fe, Co, Ni). We found that tungsten strongly enhances the solubility of iron and nickel in chromium carbide, but it does not affect the cobalt solubility. A similar stabilizing effect was predicted for molybdenum, and it can be suggested that both tungsten and molybdenum should accelerate the formation of M23C6 and influence the kinetics of carbide precipitation.