A method of forming nano-structure composite materials that have a binder material and a nanostructure fiber material is described. A precursor material may be formed using a mixture of at least one metal powder and anchored nanostructure materials. The metal powder mixture may be (a) Ni powder and (b) NiAl powder. The anchored nanostructure materials may comprise (i) NiAl powder as a support material and (ii) carbon nanotubes attached to nanoparticles adjacent to a surface of the support material. The process of forming nano-structure composite materials typically involves sintering the mixture under vacuum in a die. When Ni and NiAl are used in the metal powder mixture Ni3Al may form as the binder material after sintering. The mixture is sintered until it consolidates to form the nano-structure composite material.