Polysaccharides are often utilized as reducing and stabilizing agents and as support in the synthesis of gold nanoparticles (AuNPs). However, using approaches like spin coating or dip coating, AuNPs are generally bound to the support only by weak interactions, which can lead to decreased stability of the composite. Here, a twostage approach for the preparation of composites with covalently anchored AuNPs is proposed. First, 5 nm AuNPs with high catalytic activity for the reduction of 4-nitrophenol (TOF = 15.8 min-1) were synthesized and stabilized using fully oxidized and solubilized 2,3-dialdehyde cellulose (DAC). Next, the carbonyl groups in the shell of prepared nanoparticles were used to tether AuNPs to chitosan nanofibers with quantitative efficacy in a process that we termed "affinity anchoring". Schiff bases formed during this process were subsequently reduced to secondary amines by borohydride, which greatly improved the stability of the composite in the broad pH range from 3 to 9. The catalytic efficacy of the resulting composite is demonstrated using a model catalytic device, showing high stability, fast conversion rates, and direct reusability.