Sodium-based batteries are promising for grid storage applications due to significantly lower cost relative to lithium-based systems. To advance both solid state and redox-flow sodium-ion batteries, sodium-ion exchange membranes with high conductivity, electrochemical stability, and mechanical robustness must be developed. This study demonstrates that membranes based on poly(ethylene oxide) (PEO) can meet these requirements. To achieve high ionic conductivity, tetraethylene glycol dimethyl ether (TEGDME) is used as a plasticizer. Plasticized PEO membranes containing sodium triflate salt (NaTFS) show about 2 orders of magnitude higher conductivity compared to non-plasticized PEO membranes. Raman and FTIR spectroscopy show that the TEGDME plasticizer reduces the degree of triflate coordination by sodium cations. The mechanical properties of the membranes are improved by addition of 5 wt.% sodium caboxymethyl cellulose (CMC) without compromising the ionic conductivity.