We report a recyclable magnetic nanocatalyst, NAFe3O4@ oxalic acid@Cu(II), designed for C−C and C−S cross coupling reactions. The catalyst was synthesized via the Schikorr reaction, enabling in situ growth of Fe3O4 on natural asphalt (NA) under mild conditions with hydrogen as a benign byproduct. NA provides a stable, carbon-rich support for strong metal anchoring, while oxalic acid stabilized Cu(II) and reduces leaching. The catalyst was characterized by FT-IR, SEM, EDX, TEM, TGA, BET, VSM, XRD, and AAS. The catalyst delivered consistently high yields across a broad range of aryl halides, including substrates bearing electron-donating and electron-withdrawing groups. The process is environmentally advantageous due to mild conditions, recyclability, and reduced waste. These features highlight its potential as a sustainable and cost-effective alternative to Pd-based systems.