A more efficient use of primary energy by utilization of waste heat from electricity generation in combined heat and power plants (CHP) is essential for a sustainable reduction of CO2 emissions. Prerequisite for increasing CHP usage is an expansion of district heating networks, which allow distributing the heat to consumers.Since the construction of district heating networks requires high investments, the network expansion should concentrate on routes with a sufficiently high heat demand, in order to achieve profitability. To identify these routes, a decision support system is developed, which determines the profit-maximizing expansion of a district heating network from the perspective of the utility company. The proposed mixed-integer linear programming model determines the optimal location of heat plants, the roads to pipe and the customers to supply. The formulation as a multi period network design problem allows for a stepwise network expansion in the optimal chronological order.Crowding-out effects and thus decreasing revenues of the existing gas supply are taken into consideration. Additionally, deconstruction options for the gas network are identified.The numerical properties of the optimization model are examined through extensive benchmark calculations and compared to existing approaches for the solution of related Steiner graph problems. In a case study the applicability of the optimization model to practical problems is demonstrated, showing the effects of different demand and price scenarios.