A nanocomposite consisting of magnetite nanoparticles (Fe3O4NPs) and Au nanoparticles (AuNPs) embedded on cellulose nanocrystals (CNCs) was used as a magnetic support for the covalent conjugation of papain and facilitated recovery of this immobilized enzyme. Fe3O4NPs (10-20 nm in diameter) and AuNPs (3-7 nm in diameter) were stable and well-dispersed on the CNC surface. Energy-dispersive spectroscopy, X-ray diffraction, and Fourier transform infrared spectroscopy were used to evaluate the surface composition and structure of CNC/Fe3O4NPs/AuNPs. The nanocomposite was successfully used for the immobilization and separation of papain from the reaction mixture. The optimal enzyme loading was 186 mg protein/g CNC/Fe3O4NPs/AuNPs, significantly higher than the value reported in the literature. The activity of immobilized papain was studied by electrochemical detection of its specific binding to the Thc-Fca-Gly-Gly-Tyr-Arg inhibitory sequence bound to an Au electrode. The immobilized enzyme retained 95% of its initial activity after 35 days of storage at 4 °C, compared to 41% for its free form counterpart.