The use of nanotechnology along with the consideration of a functionalization and stabilization approach to poly(vinyl alcohol) (PVA) is considered useful for the preparation of cost-effective polyelectrolyte membranes. A set of nanocomposite and crosslinked membranes based on PVA/sulfosuccinic acid (SSA)/graphene oxide (GO) are prepared and analyzed as polyelectrolytes in direct methanol fuel cells (DMFCs). The crosslinking and sulfonation by the use of SSA enhances the stability and increase the proton-conducting sites in the PVA structure. The presence of GO augments the stability, remarkably decreases the methanol crossover, and enhances power density curves. An optimum value for proton conductivity is found for the 0.50 wt% of GO proportion, which decreases with higher concentrations of GO. Given the power density curve dependency on both the proton conductivity and the crossover reduction, the performance of these membranes as polyelectrolytes in DMFCs is strictly related to the balance between both factors. Therefore, a proportion of GO of 0.75 wt% may assure suitable proton conductivity of 3 mS cm−1 and high resistance to methanol permeability, reaching promising power density of 16 mW cm−2 with lower hydration levels.