Large spin systems can exhibit unconventional types of magnetic ordering different from the ferromagnetic or Neel-like antiferromagnetic order commonly found in spin 1/2 systems. Spin-nematic phases, for instance, do not break time-reversal invariance and their magnetic order parameter is characterized by a second rank tensor with the symmetry of an ellipsoid. Here we show direct experimental evidence for spin-nematic ordering in a spin-1 Bose-Einstein condensate of sodium atoms with antiferromagnetic interactions. In a mean field description this order is enforced by locking the relative phase between spin components. We reveal this mechanism by studying the spin noise after a spin rotation, which is shown to contain information hidden when looking only at averages. The method should be applicable to high spin systems in order to reveal complex magnetic phases.