During the last decades, municipalities have increasingly invested in new approaches for rehabilitating sewerage networks. With the increasing number of rehabilitation techniques, objectives and constraints, the number of rehabilitation scenarios rises exponentially. This article proposes an asset management approach to create long-term rehabilitation plans where different budget allocations for rehabilitation techniques are considered every year depending on performance and cost indicators. It builds long-term strategies through multiobjective black-box optimization where the impact of the budget allocations over the network life cycle is part of the decision process. It employs a pipe deterioration model based on Markov chains whose transition matrices are estimated by survival curves for different pipe cohorts. The proposed approach seeks to determine the appropriate investment (CAPEX) and operational expenses (OPEX) levels in the coming decades. It was tested with real-world data from a sewerage network in Sofia, Bulgaria, and the results show that it provides efficient long-term rehabilitation plans.