In this study, we develop a stochastic inventory model for maintenance depot of the construction machines. With this model, the inventory of critical spare parts used for the maintenance of construction machines is managed. Proposed model is a nonlinear stochastic integer optimization problem. The aim of the model is to find out reorder points, and the maximum and minimum stocking levels of critical spare parts that minimize the inventory costs. Moreover, the availability of critical spare parts is increased. The average service level and replenishment frequency constraints are also considered in the model. To solve the model, we propose a heuristic that contains a modified ABC Analysis and can be implemented with the spreadsheet applications easily. Finally, an application and cost analysis with the proposed model are performed. The comparison of total costs for the current situation and optimum inventory level that the model proposes is performed during the cost analysis. Using inventory levels and reorder amount found by the model satisfies more than 5% cost reduction.