Motivated by the importance of service quality in nowadays customer business environment, we focus on inventory optimization under probabilistic service level constraints , namely, the α service level (also known as the ready rate) or the β service level (also known as the fill rate). Under service level constraints, we consider two canonical stochastic inventory models: (i) the classical inventory control model with backlogging and (ii) the remanufacturing inventory control model with random product returns. The random demands could be non‐stationary, evolving and correlated over time. For each model, we first establish the optimality of generalized base‐stock policies, and then propose a new approximation algorithm that admits a worst‐case performance guarantee of 2. The core concept developed in this study is called the delayed forced holding and production cost , which is proven effective in dealing with service level constrained inventory systems. We also provide an efficient heuristic algorithm for the multi‐item inventory system. Our extensive computational experiments show that the proposed algorithms perform within 2% of optimality.