In this paper, we introduce the concept of complex multi-fuzzy sets (CM
k
FSs) as a generalization of the concept of multi-fuzzy sets by adding the phase term to the definition of multi-fuzzy sets. In other words, we extend the range of multi-membership function from the interval [0,1] to unit circle in the complex plane. The novelty of CM
k
FSs lies in the ability of complex multi-membership functions to achieve more range of values while handling uncertainty of data that is periodic in nature. The basic operations on CM
k
FSs, namely complement, union, intersection, product and Cartesian product are studied along with accompanying examples. Properties of these operations are derived. Finally, we introduce the intuitive definition of the distance measure between two complex multi-fuzzy sets which are used to define δ-equalities of complex multi-fuzzy sets.