This work investigates Ferro-Rock concrete as a carbon-negative alternative to ordinary Portland cement (OPC), which accounts for 5–9% of global CO₂ emissions, and evaluates its viability as a sustainable construction material. Ferro-Rock is an iron-based binder comprising recycled iron powder, fly ash, metakaolin, limestone powder, and oxalic acid. This is enhanced by a carbonation reaction in which iron particles react with CO₂ and water to form iron (II) carbonate (FeCO₃), the main binding phase, thereby locking in atmospheric CO₂. The experimental program was divided into two groups. Group 1 studied 100% Ferro-Rock binders with different types of aggregate, specimen sizes, and CO₂ curing periods (0–6 days) with a new locally manufactured stainless steel curing chamber that provided a controlled CO₂ environment of 99.9% and 1.2–1.5 bar gauge pressure. Group 2 investigated Ferro-Rock as a partial cement replacement at 0%, 5%, 10%, 15% and 20% levels of substitution with 5% increments. The 7 and 28 days of compressive, flexural and indirect tensile strengths were determined. The results showed the Ferro-Rock with 100% iron ductile waste aggregates (Mix F4) achieved a 28-day compressive strength of 5.5 MPa, 37.5% higher than the standard Ferro-Rock reference mix. The optimum replacement range of Group 2 was 5–10% with an increase in compressive strength by 5–10%, flexural strength by 11%, and indirect tensile strength by 16% over the OPC control. When replacement exceeded 25%, the bonding was weakened, and all strength measures decreased significantly, reaching a 46% reduction in compressive strength at 50% substitution. Scanning electron microscopy–energy-dispersive X-ray spectroscopy (SEM–EDS) microstructural analysis verified the gradual formation of the iron carbonate crystalline phase and provided mechanistic insights into the observed strength trends. Fully cured Ferro-Rock specimens sequestered as much as 11% CO₂ by weight, with a verifiably carbon-negative profile that no OPC-based system can match.