Existence of symmetric surface complex waves in a Goubau line—a perfectly conducting cylinder of circular cross-section covered by a concentric dielectric layer—is proved by constructing perturbation of the spectrum of symmetric real waves with respect to the imaginary part of the permittivity of the dielectric cover. Closed-form iteration procedures for calculating the roots of the dispersion equation (DE) in the complex domain supplied with efficient choice of initial approximation are developed. Numerical modeling is performed with the help of a parameter-differentiation method applied to the analytical and numerical solution of DEs.