Mechanically robust and highly permselective anion exchange membranes (AEMs) were prepared based on a graphene oxide (GO) and polybenzimidazolium nanocomposite. GO was modified via diazonium chemistry for better dispersibility and used to fabricate unsupported, nanocomposite, dense, flat sheet AEMs with different GO loadings. A fabrication route using post-casting methylation was developed to avoid GO aggregation induced by the anion exchange polymer. The even GO distribution in the membranes was mapped by energy dispersive spectroscopy (EDS) and wavelength dispersive spectroscopy (WDS). Tensile testing and nanoindentation showed that the AEMs had great mechanical strength indicated by their high ultimate tensile strength and hardness. Furthermore, the AEMs exhibited high ion exchange capacity (1.7–2.1 mmol g-1), good to exceptional permselectivity (up to 0.99) and relatively low area resistance (down to 2.9 Ω cm2). A trade-off between good selectivity and low resistance was investigated for membranes with low GO loadings (0.25–2.5%). The GO nanocomposite AEMs demonstrated excellent potential for electrodialysis.