In the simplest realization of Brownian motion, a colloidal sphere moves randomly in an isotropic fluid; its mean squared displacement (MSD) grows linearly with time tau. Brownian motion in an orientationally ordered fluid-a nematic-is anisotropic, with the MSD being larger along the axis of molecular orientation, called the director. We found that at short time scales, the anisotropic diffusion in a nematic becomes anomalous, with the MSD growing slower or faster than t; these states are respectively termed subdiffusion and superdiffusion. The anomalous diffusion occurs at time scales that correspond to the relaxation times of director deformations around the sphere. Once the nematic melts, the diffusion becomes normal and isotropic. Our experiment shows that the deformations and fluctuations of long-range orientational order profoundly influence diffusive regimes.