We have investigated the magnetic properties of the new colossal magnetoresistance oxideNaCr2O4 with the calcium-ferrite-type structure by using 23Na, 53Cr nuclear magnetic resonance(NMR) and magnetization measurements. This chromate is found to show an antiferromagneticorder with the spin moments slightly canted from the b axis at temperatures below TN=125 K. The spin structure may be governed by the competition between double-exchange ferromagneticand superexchange antiferromagnetic interactions in the double chains. The origin of the largemagnetoresistance is discussed for several scenarios such as phase separation, rearrangement of thespin structure induced by the magnetic field, and domain walls.