Novel water resistant photocatalytic composites of microfibrillated cellulose (MFC)-polyamide-amine-epichlorohydrin (PAE)-TiO2 nanoparticles (NPs) were prepared by a simple two-step mixing process. The composites produced are flexible, uniform, reproducible and reusable; they can readily be removed from the pollutant once used. Small amount of TiO2 NPs are required for the loaded composites to exhibit a remarkable photocatalytic activity which is quantified here as achieving at least 95% of methyl orange degradation under 150 min of UV light irradiation for the composite with best combination. The cellulose network combined with PAE strongly retains NPs and hinders their release in the environment. PAE dosage (10 and 50 mg/g MFC) controls the NP retention in the cellulose fibrous matrix. As TiO2 content increases, the photocatalytic activity of the composites levels off to a constant; this is reached at 2wt% TiO2 NPs for 10 mg/g PAE and 20wt% for 50 mg/g PAE. SEM and SAXS analysis confirms the uniform distribution of NPs and their formation of aggregates in the cellulose fibre network. These economical and water resistant photocatalytic paper composites made by a simple, robust and easily scalable process are ideal for applications such as waste water treatment where efficiency, reusability and recyclability are important.