Co-evolutionary algorithms deal with two co-evolving populations, each having its own objectives. The linking of the two populations comes from the fact that the evaluation of the objective of a member of the first population requires a companion member from the second population, and vice versa. These algorithms are of great interest in cooperative and competing games and search tasks in which multiple agents having different interests are in play. While there has been significant studies devoted for single-objective co-evolutionary optimization algorithms and applications, they have not been paid much attention when each population must be evolved for more than one conflicting objectives. In this paper, we propose a multi-objective co-evolutionary (MOCoEv) algorithm and present its working on two interesting problems. This proof-of-principle study suggests that the presence of multiple Pareto solutions for each population and the ensuing multi-criterion decision-making complexities make the MOCoEv research and application challenging. This paper should spur immediate further attention to multi-objective co-evolutionary problem solving studies.