We use femtosecond electron diffraction to study ultrafast lattice dynamics in the highly correlated antiferromagnetic (AF) semiconductor NiO. Using the scattering vector (Q) dependence of Bragg diffraction, we introduce a Q-resolved effective lattice temperature, and identify a nonthermal lattice state with preferential displacement of O compared to Ni ions, which occurs within ~0.3 ps and persists for 25 ps. We associate this with transient changes to the AF exchange striction-induced lattice distortion, supported by the observation of a transient Q-asymmetry of Friedel pairs. Our observation highlights the role of spin-lattice coupling in routes towards ultrafast control of spin order.