Because the velocity errors are inevitable in field data applications, direct implementation of conventional least-squares reverse time migration (LSRTM) would generate defocused migration images. Extending the model domain has the potential to preserve the data information, and reducing the extended model could provide a final image with more continuous subsurface structures for geologic interpretation. However, the computational cost and the memory requirement would be increased significantly compared to conventional LSRTM. To obtain an inversion image with better quality than conventional LSRTM, while maintaining the same computational cost and memory requirement, we have introduced random space shifts in LSRTM. The key point is to perform implicit model extension and immediate model reduction within each iteration of the inversion procedure. To be robust against the random noise during the random sampling process, we formulate the inverse problem based on a correlation objective function. Numerical examples on a simple layered model, the Marmousi model, and the SEAM model demonstrate that even when the bulk velocity errors are up to 10%, we still obtain reasonable results for subsurface geologic interpretation.