Chromium (Cr), manganese (Mn) and carbon (C) are well known alloying elements used in technologically important alloy steels and advanced high strength steels. It is known that binary Crc(x) and MnCx carbides can be formed in steels, but in this study we reveal for the first time that Cr and Mn were found combined in novel ternary cementite type (Cr, Mn)C carbides. Electron diffraction experiments showed that Cr, Mn and C formed two distinct carbide phases possessing orthorhombic and monoclinic crystal structures. Density functional theory calculations were performed on these phases and excellent agreement was found between calculations and experiments on the lattice parameters and relative atomic positions. The calculations showed that the combination of Mn and Cr resulted in a very high thermodynamic stability of the (Cr, Mn)C carbides, and that local structural relaxations are associated with carbon additions. Possible implications of these ternary carbides for novel applications in steel design and manufacturing are discussed.