Poly(vinyl alcohol) (PVA)-based ion-exchange nanofibers (IEX-NFs) and their composite polyelectrolyte membranes were prepared and characterized. The PVA-based NFs are well dispersed and form a three-dimensional network structure in the polymer matrix, Nafion. All of the prepared membranes show a similar ion-exchange capacity of ∼1.0 mmol g-1. The ionic conductivities through the PVA- b-PSS-NF/Nafion composite membranes are superior to that of the Nafion membranes, but the conductivity through the PVA-NF/Nafion composite membrane is half that of the Nafion membrane. Our electrokinetic measurements clearly indicate that a high density of ion-exchange groups on the NF surface results in a continuous ionic transport path in the polymer matrix. In addition, the mechanical strength of all of the NF-composite membranes is improved compared with that of the membranes without NF.