Partial discharge (PD) localization in substations based on the ultra-high frequency (UHF) method can be used to efficiently assess insulation conditions. Localization accuracy is affected by the accuracy of the time delay (TD) estimation, which is critical for PD localization in substations. A review of existing TD estimation methods indicates that there is a need to develop methods that are both accurate and computationally efficient. In this paper, a novel TD estimation method is proposed to improve both accuracy and efficiency. The TD is calculated using an improved cross-correlation algorithm based on full-wavefronts of array UHF signals, which are extracted using the minimum cumulative energy method and zero-crossing points searching methods. The cross-correlation algorithm effectively suppresses the TD error caused by differences between full-wavefronts. To verify the method, a simulated PD source test in a laboratory and a field test in a 220 kV substation were carried out. The results show that the proposed method is accurate even in case of low signal-to-noise ratio, but with greatly improved computational efficiency.