The fault location algorithm of an ultra-high voltage direct current (LCC-UHVDC) transmission system based on a thyristor converter plays an important role in the safe and stable operation of the smart grid. There are shortcomings of low accuracy and poor speed of fault location methods for long distance UHVDC transmission systems. Thus a double terminal traveling wave fault location method based on variational mode decomposition (VMD) and Teager energy operator (VMD) is proposed. First, the propagation characteristics of a fault voltage traveling wave in LCC-UHVDC lines are studied. Based on the characteristic that zero-mode voltage attenuates markedly with line propagation, the time-frequency characteristics of a zero-mode voltage traveling wave at a sampling point are extracted by a VMD algorithm. To solve the mode aliasing problem caused by the improper selection of VMD parameters, Kullback–Leibler (K-L) divergence is used to optimize the extracted modal indices. Then, TEO is used to extract the instantaneous energy spectrum of the decomposed signal, and the arrival time of the wave head is calibrated accurately. Finally, the fault distance is solved iteratively by the two-terminal iterative fault location method. The ±800 kV LCC-UHVDC simulation model is established in PSCAD/EMTDC for verification. The results show that the proposed method has strong robustness with different fault locations, transition resistance and fault types.