Large-scale energy storage has become the main bottleneck for increasing the percentage of renewable energy in our electricity grids. Redox flow batteries are considered to be among the best options for electricity storage in the megawatt range and large demonstration systems have already been installed. Although the full technological potential of these systems has not been reached yet, currently the main problem hindering more widespread commercialization is the high cost of redox flow batteries. Nafion, as the preferred membrane material, is responsible for about 11% of the overall cost of a 1 MW/8 MWh system. Therefore, in recent years two main membrane related research threads have emerged: 1) chemical and physical modification of Nafion membranes to optimize their properties with regard to vanadium redox flow battery (VRFB) application; and 2) replacement of the Nafion membranes with different, less expensive materials. This review summarizes the underlying basic scientific issues associated with membrane use in VRFBs and presents an overview of membrane-related research approaches aimed at improving the efficiency of VRFBs and making the technology cost-competitive. Promising research strategies and materials are identified and suggestions are provided on how materials issues could be overcome.