The technology of making micro-holes in aircraft engine parts is one of the most demanding. This stems from the application of high technological requirements for micro-hole quality and the specialized superalloys from which aircraft engine parts are manufactured. This paper presents an analysis of the effects of electrical parameters and the effect of sodium polyacrylate conductivity (10; 200; 400; 900 [µS/cm]) (used as working fluid) on the efficiency of the electrochemical discharge machining (ECDM), as well as micro-hole geometry (radial overcut, conicity). The analysis of the results covers nearly 10,000 micro-holes drilled with a 0.3 mm diameter electrode in the Inconel 718 superalloy. The analysis of the results showed that fluid conductivity affects the efficiency and stability of the ECDM process. However, higher fluid conductivities (200, 400, 900 [µS/cm]) improved radial overcut and conicity. Analysis of the results showed that Ip, DC, and GAP have the greatest impact on MRR, while CAP has the greatest impact on LTW. However, the material removal rate was improved for conductivities of 200 µS/cm and 400 µS/cm (achieving approximately 0.35 mm/s). However, for the applied fluid conductivity of 200–400 µS/cm: linear tool wear decreased to approximately 1 mm, radial overcut increased slightly to approximately 0.6 mm, and conicity decreased to within the range of 0.04–0.05 mm. Analysis of the results also showed how the range of electrical parameter values should be reduced for further drilling tests.