<p>Stone matrix asphalt (SMA) relies on a high-quality aggregate structure and a rich mortar to provide sustainable performance benefits, including superior distress resistance, enhanced acoustic properties, and good drainage. Thus, SMA ensures pavement longevity, improves community livability and fosters safety, making it a premium paving mixture for heavy-duty pavements. However, SMA has a high production cost due to high binder content and high-quality aggregate requirement, warranting a continual search for cost-reduction strategies. This study investigated the feasibility of fully replacing granite aggregate and hydrated lime with steel slag aggregate (SSA) and palm kernel shell ash (PKSA) in SMA to enhance its sustainability and minimize cost. The novelty lies in the full incorporation of both materials simultaneously to examine their synergistic impact on SMA characteristics. Aggregate property testing qualified both materials for SMA production. Two sets of SMA were prepared: (a) a waste-based SMA in which steel slag served as coarse aggregate and PKSA as fine aggregate and filler, (b) a control SMA that utilized granite and hydrated lime. Both mixtures had identical gradation and optimum binder content; however, the waste-based mixture’s binder absorption was greater. The waste-based SMA showed improved cracking, rutting, and moisture damage resistance over the control SMA, with 9% higher cracking resistance, 41% greater rutting resistance, and 8% better moisture damage resistance. Both mixtures met Marshall stability, flow, and Cantabro durability criteria. However, the waste-based SMA showed 16% lower stability, 17% higher flow, and twice the Cantabro loss compared with the control. Factors differentiating the performance characteristics of both mixtures have been discussed. Overall, SSA and PKSA can fully replace granite and hydrated lime in SMA to yield similar or better performance as conventional SMA. Field validation of the waste-based SMA characterization results is recommended.</p>