While both periodic narrowband noise and white noise are significant sources of interference in the detection and localization of partial discharge (PD) signals in power cables, existing research has focused nearly exclusively on white noise suppression. This paper addresses this issue by proposing a new signal extraction method for effectively detecting random PD signals in power cables subject to complex noise environments involving both white noise and periodic narrowband noise. Firstly, the power cable signal was decomposed using complete ensemble empirical mode decomposition with adaptive noise (CEEMDAN), and the periodic narrowband noise and frequency aliasing in the obtained signal components were suppressed using singular value decomposition. Then, signal components contributing significantly to the PD signal were determined according to the cross-correlation coefficient between each component and the original PD signal, and the PD signal was reconstructed solely from the obtained significant components. Finally, the wavelet packet threshold method was used to filter out residual white noise in the reconstructed PD signal. The performance of the proposed algorithm was demonstrated by its application to synthesized PD signals with complex noise environments composed of both Gaussian white noise and periodic narrowband noise. In addition, the time-varying kurtosis method was demonstrated to accurately determine the PD signal arrival time when applied to PD signals extracted by the proposed method from synthesized signals in complex noise environments with signal-to-noise ratio (SNR) values as low as −6 dB. When the SNR was reduced to −23 dB, the arrival time error of the PD signal was only one sampling point.