We describe a strategy to prepare stable and active nanocomposites of enzymes and carbon nanotubes by covalently immobilizing enzymes onto multi-walled carbon nanotubes (MWNTs). Various enzymes were immobilized onto oxidized MWNTs using carbodiimide chemistry to prepare water-soluble MWNT-enzyme conjugates. The immobilized enzymes were highly active and stable even under harsh conditions of temperature and organic solvents. The MWNT-enzyme conjugates were incorporated into polymers and gels to generate highly stable bioactive materials. Conjugates of soybean peroxidase (SBP) and MWNTs (MWNT-SBP) were then incorporated into poly(methyl methacrylate) (pMMA) to form thermostable polymeric films for bioremediation of phenolics and dyes. Such highly stable biocatalytic nanocomposites of multi-walled carbon nanotube and enzymes will have a profound impact on various fields such as biotransformations, bioremediation, biosensing, diagnostics, and biomedical devices.