Variations of the free volume, O2 permeability, and structure of the Nafion membrane upon ion exchange of H+ with Na+ and K+ were studied. The free volume was quantified using the positron annihilation lifetime (PAL) technique, whereas the polymer structure was characterized by dynamic mechanical analysis (DMA), nanoindentation, and wide-angle X-ray diffraction (WAXD). It was found that the ion exchange significantly expands the free volume and at the same time decreases the O2 permeability. This is opposed to the simple free volume model in which the structure with less open volume is more amenable to lower permeability. Comparison of experimental data collected by different techniques revealed that not only the free volume but also the polymer stiffness plays an essential role in O2 permeation.