Soda residue is the solid waste generated during the ammonia-soda process for soda ash, while there is no effective treatment and utilization disposal method. In order to maximize residue utilization, soda residue, blast furnace slag, steel slag, and desulfurization gypsum were used as composite cementitious material, and iron tailing sand and waste rock were used as aggregate to prepare clinker-free concrete. Results show that by mixing 30% soda residue, 45% blast furnace slag, 15% steel slag, and 10% desulfurization gypsum, the 28-day compressive strength of the clinker-free concrete could reach up to 38.33 MPa. Hydration products and hydration process of the composite cementitious material were studied through XRD, SEM-EDS, TG-DSC, and IR, and results show that the hydration products of the composite cementitious material were mainly C-S-H gel, ettringite (AFt), and Friedel’s salt (FS). The synergistic reaction mechanism between the raw materials was analyzed to further understand the formation process of the hydration products. Moreover, durability analysis of all-solid waste concrete demonstrates that the concrete had good frost and carbonation resistance, while its dry shrinkage resistance and sulfate attack resistance were poor. Finally, the preparation conditions, application scope, and application prospects of the soda residue clinker-free concrete were analyzed, which provides an in-depth scientific basis for the harmless and resource utilization of soda residue.