This work considers an operational management optimization of wastewater treatment plants. We present a new, CMDP-based optimization model for this problem, as well as a decomposition algorithm for solving it. From a theoretical perspective, we show that the algorithm’s solution is near-optimal and provides an upper bound for its result. For practical considerations, we applied our approach to the plant of a medium-sized European city. We achieved a significant reduction in costs as well as an improvement in compliance with local regulations.