As one of the most promising micro-machining methods, electrochemical micro-machining is widely used in the field of metal micro-structures. The electrochemical micro-milling on Nickel-base superalloy by using high-speed spiral electrode was studied in detail. Firstly, the electric field and flow field models of micro-electrochemical milling are established and analyzed by the finite element method. Then, the milling profile was predicted and the effect of high-speed rotation of electrodes on electrolyte promotion and secondary electrolysis prevention were analyzed. Secondly, the influence of the main machining parameters, such as rotating speed, electrical parameters, and feed rate on machining precision and efficiency was analyzed experimentally. Finally, by optimizing the machining parameters, a series of micro-graphic structures with a width of about 150 μm were obtained on Nickel-base superalloy 718 by using the spiral electrode with a diameter of 100 μm. The experimental and simulation results show that the high-speed rotation of electrodes can greatly improve the machining efficiency and stability. It was proved that micro-electrochemical milling with the high-speed rotating electrode technique is an effective method for machining micro-metal parts.