Nanocrystallites, acting as physical cross-links in Nafion membranes, play a crucial role in building blocks for improving mechanical durability and stopping fuel crossover. However, Nafion membranes suffer from low crystallinity due to the irregular pendent side chains, which hinder self-aggregation of the poly(tetrafluoroethylene) (PTFE) backbones. For the first time, a molecular gelator was introduced in the membrane casting process to enhance the rate of self-assembly of PTFE backbones so as to increase the membrane’s crystallinity as well as proton conductivity without sacrificing the purity of Nafion. The molecular gelator used was 3,4-dimethylbenzaldehyde (DMBA). Addition of 0.5 wt % DMBA led to a 42% increase in crystallinity, a 32% increase in yield strength, a 22% increase in tensile modulus and an 18% increase in proton conductivity at 60 °C and 90% relative humidity. Additionally, the membrane electrode assembly (MEA) prepared from the membranes cast from the solution containing 0.5 wt % DMBA also showed an increase of 17% in maximum power density in comparison to the MEA prepared from pure Nafion membrane in a single cell polarization test without any external humidification. Transmission electron microscopy (TEM) and molecular dynamics simulation were used to elucidate the structural changes in Nafion membrane due to the introduction of DMBA. It was observed that the presence of DMBA gives wider crystalline regions under TEM. The molecular dynamics simulation at 500 K shows that the PTFE backbones become elongated in the presence of DMBA due to the enhanced mobility. This is consistent with the observed increase in crystallinity in the membrane as it means reduced entropic change upon crystallization.