Surface morphology is one of the critical parameters that affect the frictional behavior of two contacting bodies in relative motion. It is important because the real contact area as well as the contact stiffness is dictated by the micro- and nano-scale geometry of the surface. In this regard, the frictional behavior may be controlled by varying the surface morphology through nano-structuring. In this study, molecular dynamics simulations were conducted to investigate the effects of contact area and structural stiffness of corrugated nano-structures on the fundamental frictional behavior at the atomic-scale. The nano-structured surface was modeled as an array of corrugated carbon atoms with a given periodicity. It was found that the friction coefficient of the nano-structured surface was lower than that of a smooth surface under specific contact conditions. The effect of applied load on the friction coefficient was dependent on the size of the corrugation. Furthermore, stiffness of the nano-structure was identified to be an important variable in dictating the frictional behavior.