Locating the partial discharge (PD) source is one of the most effective means to locate local defects in power cable lines. The sampling rate and the frequency-dependent characteristic of phase velocity have an obvious influence on localization accuracy based on the times of arrival (TOA) evaluation algorithm. In this paper, we present a cross-correlation algorithm based on propagation distance to locate the PD source in cable lines. First, we introduce the basic principle of the cross-correlation function of propagation distance. Then we verify the proposed method through a computer simulation model and investigate the influences of propagation distance, sampling rate, and noise on localization accuracy. Finally, we perform PD location experiments on two 250 m 10 kV XLPE power cables using the oscillation wave test system. The simulation and experiment results indicate that compared with traditional TOA evaluation methods, the proposed method has superior locating precision.