The thermoelectric properties of sintered bodies of NaCo₂O₄, which is so far the most promising p-type candidate for oxide thermoelectric material, are investigated in terms of their sintering conditions. Double-step sintering, for which single-phase NaCo₂O₄ obtained by calcination and sintering with addition of 10% excess of Na each time is re-ground and sintered again, is revealed to attain a marked improvement in the thermoelectric performance of the oxide. The improvement is due to increase in both Seebeck coefficient and electrical conductivity, and is attributed to a distinct enhancement of the two-dimensionality in the crystallites constituting the sintered body. The oxide sintered body consequently attains the figure-of-merit of 0.88×10^-3K^-1 at 600°C, and the maximum ZT of 0.78 at 800°C.