The sodium thermal electrochemical converter (Na-TEC) is a heat engine that generates electricity through the isothermal expansion of sodium ions. The Na-TEC is a closed system that can theoretically achieve conversion efficiencies above 45% when operating between thermal reservoirs at 1150 K and 550 K. However, thermal designs have confined previous single-stage devices to thermal efficiencies below 20%. To mitigate some of these limitations, we consider dividing the isothermal expansion into two stages; one at the evaporator temperature (1150 K) and another at an intermediate temperature (650 K-1050 K). This dual-stage Na-TEC takes advantage of regeneration and reheating, and could be amenable to better thermal management. Herein, we demonstrate how the dual-stage device can improve the efficiency by up to 8% points over the best performing single-stage device. We also establish an application regime map for the single- and dual-stage Na-TEC in terms of the power density and the total thermal parasitic loss. Generally, a single-stage Na-TEC should be used for applications requiring high power densities, whereas a dual-stage Na-TEC should be used for applications requiring high efficiency.