Sodium-based batteries are promising for grid-storage applications because of significantly lower cost compared to lithium-based systems. The advancement of solid-state and redox-flow sodium-ion batteries requires sodium-ion exchange membranes with high conductivity, electrochemical stability, and mechanical robustness. This study demonstrates that membranes based on poly(ethylene oxide) (PEO) can meet these requirements. Membranes plasticized with tetraethylene glycol dimethyl ether (TEGDME) achieve high ionic conductivity. Plasticized PEO membranes containing sodium triflate salt (NaTFS) show about 2 orders of magnitude higher conductivity compared to nonplasticized PEO membranes. Results from vibrational spectroscopy and differential scanning calorimetry describe the coordination chemistry in these multiphase materials and explain the mechanisms behind the increased conductivity. The mechanical properties of the membranes improve by addition of 5 wt % sodium carboxymethyl cellulose (CMC) without compromising the conductivity or electrochemical stability against sodium metal. The optimized membrane is an excellent candidate for low-cost energy storage systems that operate over a wide voltage window near ambient temperature.