NaCr2O4 was recently discovered using a high-pressure synthesis to occur in a calcium-ferrite-type structure, where one-dimensional electronic correlations and geometrical frustrations can coexist. It shows unconventional colossal magnetoresistance (CMR) at temperatures below antiferromagnetic ordering temperature of T N = 125 K. The CMR effect is progressively enhanced with decreasing temperature with no thermal or field hysteresis. Spin frustration and holes in oxygen ions may be the origins of the observation of the CMR effect in the compound.