The process of obtaining chemically bonded phosphate ceramics generally involves the use of metallic oxides, the preparation of which consumes high quantities of energy. The present study proposes a method to recycle slags generated by a steel production process that is widely used across the world—the electric arc furnace. A chemically bonded phosphate ceramic is produced by exploiting the high content of metals present in the slag, realizing the conditions to mitigate the environmental impact of the industrial by-product. In situ infrared spectroscopy, isothermal conduction calorimetry, and X-ray diffraction revealed that the setting reaction involves the formation of amorphous products in the form of metallic phosphate hydrates and a fraction of calcium silicate hydrates similar to those found in portland cement. This phosphate matrix allows the effective immobilization of heavy metals in the slag, such as Cr and As. According to the results of mechanical tests, which showed compression resistance of 15–25 MPa, and leaching tests, slag-based phosphate cement can be used without restrictions as a construction material for applications such as mortars or bricks.