Water pollution, particularly industrial wastewater, is a major environmental issue due to its adverse effects. Sustainable wastewater treatment is one of the major challenges of this century, as well as sustainable production of polymer membranes for it. One of alternative methods is the production of polyelectrolyte complex (PEC) membranes based on aqueous phase separation approach. In this work, nanofiltration membranes from PEC of poly(sodium-p-styrenesulfonate) (PSS)/poly(diallyldimethylammonium chloride) (PDADMAC) with improved transport characteristics were developed via salt-dilution induced phase separation for enhanced water treatment from food anionic dyes and heavy metal ions. The improvement was carried out by variation of monomer ratio (40–60 wt% PSS), introduction of graphene oxide (GO, 3–7 wt%) and PSS with lower molecular weight (70 kDa) in PEC, and combination of all optimal modification conditions. The structural features of PEC-based membranes were studied by FTIR, NMR, Raman, XPS spectroscopies, scanning electron and atomic force microscopies, and thermogravimetric analysis. A theoretical analysis using quantum chemical calculations was carried out to confirm the influence of polymer interactions with components on changes in membrane properties. For PEC membranes with PSS/PDADMAC monomer ratio of 40/60, modified with 5 wt% GO and with the introduction of both PSS (70 kDa) with GO, led to more than 3.5 and 5 times higher permeance, respectively, and enhanced rejection compared to the unmodified PEC membrane in nanofiltration of dye and heavy metal ion solutions.