In present work, micro-deep holes on AISI 304 stainless steel were drilled via electrical discharge machining (EDM) method. In the first phase of this work, the effect of test parameters on the drilling performance and the profile of drilled holes were investigated experimentally. Test parameters including discharge current, dielectric spray pressure and electrode tool rotational speed were taken and then the machining rate (MR), electrode wear rate (EWR), average over-cut (AOC) and taper angle (TA) were measured in order to assess the drillability of EDM. After experimental study, an analysis of variance was performed to identify the effect of the importance of test parameters on experiment outputs. In the second phase of this study, optimum process parameters were determined using signal-to-noise analysis and response surface methodology (RSM) for mono-optimization and multi-response optimization, respectively. In the last phase, regression analysis and artificial neural network (ANN) models for predicting the MRR, EWR, AOC and TA. As a result of experimental analysis, discharge current was the most important parameter for micro-drilling with EDM. It was found out that this parameter influenced positively MR, while it has negatively an effect on EWR, AOC and TA. Mathematical model based on ANNs exhibited a successful performance for predication of outputs. Optimum process parameters which were discharge current of 10.18 , dielectric liquid pressure of 58.78 bar and electrode tool rotational speed of 100 rpm for multi-objective optimization were determined through RSM with desirability function analysis in micro-deep hole EDM drilling of AISI 304 stainless steel.