We here report three different approaches to prepare silica-polyelectrolyte complexes for mechanical strengthening of cotton fibers. In the first approach, polyvinylpyrrolidone (PVP) was used as a stabilizing polymer to delay the adsorption of a poly(quaternary ammonium) species, PQA (a copolymer of dimethylamine and epichlorohydrin), on the surface of silica. In the second approach cationic starch (CS), which is a branched polyelectrolyte, was used and the adsorption of CS resulted in formulations with good colloidal stability. The third approach was based on reduction of the charge density of silica to prevent PQA adsorption. Lowering the pH reduced the surface charge of the silica and enabled control of the adsorption. As a result, the aggregation was prevented and only a thin layer of polymer adsorbed. For all formulations a second polyelectrolyte, carboxymethyl cellulose (CMC) was subsequently adsorbed on the cationic polyelectrolyte layer. The silica/polyelectrolyte formulations were evaluated by dynamic light scattering (DLS). The obtained formulations were applied on model surfaces of degraded painting canvas. The performance of the silica particles coated either with one cationic polyelectrolyte and or with a layer of cationic polyelectrolyte followed by a layer of anionic polyelectrolyte were assessed by tensile testing and the morphology of the treated samples was investigated with SEM. The particles coated with a single cationic layer increased the maximum load at break by 29% at the cost of a reduction in strain. The particles coated with a double layer increased the maximum load to a lesser extent; however, higher values of strain were recorded. For all systems the mass uptake was limited to around 5 wt%.