We report on the ultrafast dynamics of magnetic order in a single crystal of CuO at a temperature of 207 K in response to strong optical excitation using femtosecond resonant x-ray diffraction. In the experiment, a femtosecond laser pulse induces a sudden, nonequilibrium increase in magnetic disorder. After a short delay ranging from 400 fs to 2 ps, we observe changes in the relative intensity of the magnetic ordering diffraction peaks that indicate a shift from a collinear commensurate phase to a spiral incommensurate phase. These results indicate that the ultimate speed for this antiferromagnetic reorientation transition in CuO is limited by the long-wavelength magnetic excitation connecting the two phases.