Natural-based polyelectrolytes (PELs), with all the advantages coming from being produced from renewable and biodegradable sources, are a potential solution for the removal of dyes from wastewater. In this work, surplus Eucalyptus bleached cellulose fibres from a paper mill were modified to increase the charge and solubility of cellulose. First, reactive aldehyde groups were introduced in the cellulose backbone by periodate oxidation of cellulose. Further modification with alkylammonium produced positively charged cellulose-based PELs. The final products were characterized by several analytical techniques. The PEL with the highest substitution degree of cationic groups was evaluated for its performance in decolouration processes, bentonite being used as aid. This was found to be effective for colour removal of either anionic or cationic dyes. Bio-PELs can thus be considered as very favourable eco-friendly flocculation agents for decolouration of harsh effluents from several industries, considering their biodegradable nature and thus the ability to produce less sludge.