Evidence theory is an effective methodology for modeling and processing uncertainty that has been widely applied in various fields. In evidence theory, a number of distance measures have been presented, which play an important role in representing the degree of difference between pieces of evidence. However, the existing evidential distances focus on traditional basic belief assignments (BBAs) modeled in terms of real numbers and are not compatible with complex BBAs (CBBAs) extended to the complex plane. Therefore, in this article, a generalized evidential distance measure called the complex evidential distance (CED) is proposed, which can measure the difference or dissimilarity between CBBAs in complex evidence theory. This is the first work to consider distance measures for CBBAs, and it provides a promising way to measure the differences between pieces of evidence in a more general framework of complex plane space. Furthermore, the CED is a strict distance metric with the properties of nonnegativity, nondegeneracy, symmetry, and triangle inequality that satisfies the axioms of a distance. In particular, when the CBBAs degenerate into classical BBAs, the CED will degenerate into Jousselme et al.'s distance. Therefore, the proposed CED is a generalization of the traditional evidential distance, but it has a greater ability to measure the difference or dissimilarity between pieces of evidence. Finally, a decision-making algorithm for pattern recognition is devised based on the CED and is applied to a medical diagnosis problem to illustrate its practicability.