Metal-metal fiber-reinforced composites with high ductility and high strength have previously been produced by deformation processing Cu and Ti binary alloys. Mg-X alloys (where X =Ti, Nb, and Fe) have also been deformation processed to produce high-strength, high-ductility composites which have stable microstructures when exposed to 400°C for 500 hours. In these experiments, metal-metal composites consisting of a matrix of Mg or Mg-12wt%Li-2wt%Nd were produced by infiltrating a 10-20% dense steel wool with the molten matrix alloy. The Mg/IOSW material did not roll well, even at 300°C. However, the Mg-12Li-2Nd/20SW had excellent ductility at room temperature and it was reduced 99.6% without annealing, producing a composite sheet with highly elongated, nano-scale steel filaments. These Mg-based composites were evaluated by mechanical testing, microscopy, and high-temperature annealing to determine the relation between processing, microstructure, and properties. It is believed that deformation processing can be used to successfully develop a Mg-based composite with low density, high strength, high ductility, high fracture toughness, and excellent thermal stability. Such a Mg-based composite would represent a truly unique method for producing commercially viable structural materials.