Industrial wastewater poses a significant environmental challenge due to its harmful effects. The development of sustainable membrane processes for water treatment and the environmentally friendly production of polymer membranes is one of the major challenges of our time. An alternative approach is to prepare polyelectrolyte complex (PEC) membranes using the aqueous phase separation (APS) method without the use of toxic solvents. In this work, PEC nanofiltration membranes of poly(sodium-p-styrenesulfonate) (PSS)/polyethylenimine (PEI) modified with carbon nanoparticles (graphene oxide, polyhydroxylated fullerene (HF), multi-walled carbon nanotubes) were developed for enhanced water treatment from anionic food dyes and heavy metal ions. The effect of varying the PSS/PEI monomer ratio, carbon nanoparticles, the content of the optimal HF modifier, and the cross-linking agent on the membrane properties was studied in detail. The changes in the structure and physicochemical properties of the PEC-based membranes were investigated using spectroscopic, microscopic, thermogravimetric analysis methods, and contact angle measurements. The PSS and PEI interactions during PEC formation and the effect of PEI protonation on membrane properties were investigated using computational methods. The optimal cross-linked PEC/HF(1%) (1:1.75 PSS/PEI) membrane had more than 2 times higher permeability compared to the pristine PEC membrane, with dye and heavy metal ion rejection of 99.99 and >97%, respectively.