We show that relative earthquake location using double-difference methods requires an accurate knowledge of the velocity structure throughout the study region to prevent artifacts in the relative position of hypocenters. The velocity structure determines the ray paths between hypocenters and receivers. These ray paths, and the corresponding ray take-off angles at the hypocenters, determine the partial derivatives of travel time with respect to the hypocentral coordinates which form the inversion kernel that maps double-differences into hypocentral perturbations. Thus the large-scale velocity structure enters into the core of the double-difference technique. By employing a 1D layered model with sharp interfaces to perform double-difference inversion of synthetic data generated using a simple, 1D gradient model; we show that inappropriate choice of the velocity model, combined with unbalanced source-receiver distributions, can lead to significant distortion and bias in the relative hypocenter positions of closely spaced events.