Patients in intensive care units need special attention. Therefore, nurses are one of the most important resources in a neonatal intensive care unit. These nurses are required to have highly specialized training. The random number of patient arrivals, rejections, or transfers due to lack of capacity (such as nurse, equipment, bed etc.) and the random length of stays, make advanced knowledge of the optimal nurse a requirement, for levels of the unit behave as a stochastic process. This stochastic nature creates difficulties in finding optimal nurse staffing levels. In this paper, a stochastic approximation which is based on the required nurse: patient ratio and the number of patients in a neonatal intensive care unit of a teaching hospital, has been developed. First, a meta-model was built to generate simulation results under various numbers of nurses. Then, those experimented data were used to obtain the mathematical relationship between inputs (number of nurses at each level) and performance measures (admission number, occupation rate, and satisfaction rate) using statistical regression analysis. Finally, several integer nonlinear mathematical models were proposed to find optimal nurse capacity subject to the targeted levels on multiple performance measures. The proposed approximation was applied to a Neonatal Intensive Care Unit of a large hospital and the obtained results were investigated.