Micro-structured surfaces possess excellent properties of friction, lubrication, drag reduction, antibacterial, and self-cleaning, which have been widely applied in optical, medical, national defense, aerospace fields, etc. Therefore, it is requisite to study the fabrication methods of micro-structures to improve the accuracy and enhance the performance of micro-structures. At present, there are plenty of studies focusing on the preparation of micro-structures; therefore, systematic review of the technologies and developing trend on the fabrication of micro-structures are needed. In present review, the fabrication methods of various micro-structures are compared and summarized. Specially, the characteristics and applications of ultra-precision machining (UPM) technology in the fabrication of micro-structures are mainly discussed. Additionally, the assistive technologies applied into UPM, such as fast tool servo (FTS) technology and slow tool servo (STS) technology to fabricate micro-structures with different characteristics are summarized. Finally, the principal characteristics and applications of fly cutting technology in manufacturing special micro-structures are presented. From the review, it is found that by combining different machining methods to prepare the base layer surface first and then fabricate the sublayer surface, the advantages of different machining technologies can be greatly exerted, which is of great significance for the preparation of multi-layer and multi-scale micro-structures. Furthermore, the combination of ultra-precision fly cutting and FTS/STS possess advantages in realizing complex micro-structures with high aspect ratio and high resolution. However, residual tool marks and material recovery are still the key factors affecting the form accuracy of machined micro-structures. This review provides advances in fabrication methods and assistive technologies of micro-structured surfaces, which serves as the guidance for both fabrication and application of multi-layer and multi-scale micro-structures.