This paper presents a novel perspective to the use of multi-objective optimization and in particular evolutionary multi-objective optimization (EMO) as a measure of complexity. We show that the partial order feature that is being inherited in the Pareto concept exhibits characteristics which are suitable for studying and measuring the complexities of embodied organisms. We also show that multi-objectivity provides a suitable methodology for investigating complexity in artificially evolved creatures. Moreover, we present a first attempt at quantifying the morphological complexity of quadruped and hexapod robots as well as their locomotion behaviors.