An alternative to conventional methods for mine tailings disposal is stabilization with alkali-activated binders (AABs), developed from agro-industrial waste. Despite increasing interest in this topic, there is still a lack of studies focusing on the stabilization of iron ore tailings (IOTs) using AABs, particularly those that combine the characterization of cementitious gels with an evaluation of leaching behavior. This study assessed the strength, mineralogy, and leaching performance of IOTs stabilized with AABs formulated from rice husk ash (RHA) and hydrated eggshell lime (HEL), using sodium hydroxide as the alkaline activator. Tests included unconfined compressive strength (UCS), X-ray diffraction (XRD), Fourier-transform infrared spectroscopy (FTIR), and metal leaching analyses. The IOT–AAB mixture with the highest AAB content and dry unit weight achieved an average UCS of 2.14 MPa after 28 days of curing. UCS increased with AAB content, followed by dry unit weight and curing time, the latter showing a non-linear influence. The formation of C–S–H gel was confirmed after 28 days, while N–A–S–H gel was detected as early as 7 days of curing. The cemented IOT–AAB mixtures showed no metal toxicity and effectively encapsulated barium originating from the RHA.