In this work, graphene oxide (GO) nano-additive was incorporated into polyelectrolyte complex (PEC) to prepare PEC-GO water selective membrane for water desalination process. The synthesized thin film composites consisted of a PEC-GO separation layer, a microporous poly(vinylidene fluoride) layer and a non-woven substrate. Glutaraldehyde was used as a cross-linker to enhance mechanical strength of the composite membranes. The resulting membranes were investigated on nanofiltration systems to examine the water permeability and salt rejection efficiency. The results showed that 100 ppm GO in the PEC exhibited a high desalination efficiency on 1000 ppm NaCl solution. This composite rendered permeance values in the range of 69.3–88.9 kg/m2hMPa for various salt solutions. The Na2SO4 solution resulted in the highest rejection ratio of 62.1%, followed by the NaCl rejection (45%). The MgCl2 and MgSO4 solutions had lower rejections of 12.2 and 22.0%. It seems that the PEC-GO composite was more efficient in removing monovalent cation while maintaining high filtration flux.