Nanostructured surfaces usually exhibit complicated morphologies that cannot be described in terms of Euclidean geometry. Simultaneously, they do not constitute fully random noise fields to be characterized by simple stochastics and probability theory. In most cases, nanomorphologies consist of complicated mixtures of order and randomness, which should be described quantitatively if one aims to control their fabrication and properties. In this work, inspired by recent developments in complexity theory, we propose a method to measure nanomorphology complexity that is based on the deviation from the average symmetry of surfaces. We present the methodology for its calculation and the validation of its performance, using a series of synthetic surfaces where the proposed complexity measure obtains a maximum value at the most heterogeneous morphologies between the fully ordered and fully random cases. Additionally, we measure the complexity of experimental micro and nanostructured surfaces (polymeric and metallic), and demonstrate the usefulness of the proposed method in quantifying the impact of processing conditions on their morphologies. Finally, we hint on the relationship between the complexity measure and the functional properties of surfaces.