The surface integrity and machining accuracy of thin-walled micro parts are significantly affected by micro-milling parameters mostly because of their weak stiffness. Furthermore, there is still a lack of studies focusing on parameters optimization for the fabrication of thin-walled microscale parts. In this paper, an innovative approach is proposed for the optimization of machining parameters with the objectives of surface quality and dimension accuracy, which integrates the Taguchi method, principal component analysis method (PCA) and the Non-dominated sorting genetic algorithm (NSGA-II). In the study, surface arithmetic average height Sa, surface root mean square height Sq, and 3-D fractal dimension Ds are selected to evaluate surface quality. Then micro-milling experiments are conducted based on the Taguchi method. According to the experimental results, the significance of machining parameters can be determined by range analysis. Besides, regression models for the responses are developed comparatively, and the PCA method is employed for dimension reduction of the optimization objective space. Finally, two combinations of machining parameters with the highest satisfaction are obtained through NSGA-II, and verification experiments are carried out. The results show that the surface quality and dimension accuracy of the thin-walled microscale parts can be simultaneously improved by using the proposed approach.