An experimental investigation was performed for investigating the tribological performance of micro-dimple surface texture patterns on a cylindrical surface in a realistic operating environment of starved lubrication. Micro-dimples were generated by a dual-frequency surface texturing method, in which a high-frequency (16.3 kHz) three-dimensional (3D) vibration and a low-frequency (230 Hz) one-dimensional (1D) vibration were applied at the tool tip simultaneously, resulting in the generation of the hierarchical micro-dimples in a single step. Rotating cylinder-on-pin tribological tests were conducted to compare the tribological performance of the non-textured reference specimen and micro-dimple samples. The effect of surface textures generated with various shape parameters (long drop and short drop), dimension parameters (length and surface texture density), and operation parameters (load and sliding velocity) on the tribological performance was evaluated. Stribeck curves indicate that the hierarchical micro-dimples exhibit a lower coefficient of friction than the reference specimen in the high contact-pressure regions. It is also observed that variation in the length of a micro-dimple, the shape effect, is the major factor affecting the friction response of the textured surfaces. The generation of additional hydrodynamic pressure and lift effect by hierarchical structures is the main reason for the improved performance of hierarchical micro-dimple surfaces.