Two samples of oxidized sodium cobalt oxide, NaxCoO2, where x=0.3 and 0.7, have been studied by variable-temperature wide-line Na-23-NMR. All spectra exhibit a substantially paramagnetic-shifted response characterized by 2nd-order quadrupole broadening and a diamagnetic-shifted weaker response. The paramagnetic shifts are attributed to spins localized on cobalt atoms. The 2nd-order quadrupolar splitting is resolved for x=0.7; whereas the lineshapes obtained for x=0.3 do not show the resolution and indicate a more symmetric sodium environment and/or a greater degree of ion mobility, Lineshapes for the two compositions behave somewhat differently as the temperature is changed, although both samples exhibit gradual line-narrowing over the entire range (-150 to 100 degrees C). Spin-lattice relaxation time measurements reflect the presence of inequivalent sodium environments, with one distribution of sodium environments characterized by long relaxation times (10 ms-200 ms) and another set of environments characterized by much shorter times (< 500 mu s).