To solve the problem that the adaptability of partial discharge signals is not insufficient in denoising process, a new algorithm of partial discharge thresholding denoising based on complete ensemble empirical mode decomposition and ensemble empirical mode decomposition is proposed. Firstly, the discharge signals should be decomposed by CEEMD. Secondly, the intrinsic mode functions which have been broken out by CEEMD should be decomposed by EEMD. Thirdly, the thresholding denoising of decomposed signals is carried on based on the knowledge of mathematical statistics. This paper makes use of the new algorithm to denoise for simulation signals and measured signals and to compare with the conventional wavelet denoising algorithm. The simulation results and experimental results show that the thresholding denoising algorithm for partial discharge based on CEEMD-EEMD gets a satisfactory effect, showing validity of the method, which provides a new way for the partial discharge signals to denoise.