This research reports the fabrication of nanocomposite cation exchange membranes (CEMs) by incorporating negatively charged graphene-based nanomaterials into a non-charged poly(vinylidene fluoride) (PVDF) matrix using a mold-casting technique developed in-house. Graphene oxide (GO) or reduced graphene oxide (rGO) nanosheets were modified into ion exchange group carriers using a sulfonic group-bearing agent based on poly(sodium 4- styrenesulfonate)/3,4-dihydroxy-L-phenylalanine (PSS/L-DOPA) (SGO or SrGO). Such modified nanosheets provide the ion exchange capabilities in SGO/PVDF and SrGO/PVDF nanocomposite CEMs, respectively. Both nanocomposite CEMs displayed lower linear swelling ratios which are good for membrane stability. This was due to the presence of the nanomaterials which acted as pore fillers and increased the stiffness of the nanocomposite membranes. The ion exchange capacity (IEC) and permselectivity of the SGO/PVDF_45 CEMs were slightly higher than the values for the SrGO/PVDF_45 CEM. It was found that the SrGO additive increased the area resistance of the nanocomposite CEM. However, SrGO/PVDF_45 CEM demonstrated a higher current efficiency (7.5% higher than SGO/PVDF_45), which could be attributed to the improved electronic conductivity of rGO. It was found that both nanocomposite CEMs performed well in electrodialysis experiments to achieve the substantial salt removal rates, although the energy consumption results of the novel nanocomposite CEMs were higher than the conventional polymeric CEM. The above research results have successfully demonstrated the concept of fabricating nanocomposite cation exchange membranes (CEMs) for electrodialysis applications by employing negatively charged graphene-based nanomaterials as ion exchange carriers.