A new systematic methodology for designing wastewater and heat exchange networks for process industries involving effluent streams containing multiple contaminants is proposed. A simultaneous optimization approach mathematically combines the problems of wastewater and heat exchanger network optimization into a single step. This process includes two global iterations of a similar two-stage approach and optimizes networks for water and heat exchange simultaneously based on cost estimates. The objective function is to minimize the total annual cost of the wastewater and heat exchange network design which is subject to the mass and energy balance constraints on all the pertinent flows and to constraints related to the concentrations of contaminants. The proposed method employs a strategy to address a mixed integer non-linear programming (MILNP) formulation. This approach was applied to optimize the wastewater and heat exchanger networks connecting oil refinery processes, which included CDU, HDS, and desalter units, and three contaminants: hydrocarbons, H2S, and salt. In order to validate the proposed method, the solutions from four different optimization problems were compared. Simultaneous optimization reduced total costs by 76.4% compared to the base case (optimized solution without water reusing or heat exchange), in which water recycling and heat exchange were not employed, and by 3.9% compared to case 3 (wastewater reusing and heat exchanger networks optimized using the two-stage optimization approach). The novel method of simultaneous optimization was not only simpler than the established sequential design method but also less expensive than the sequential method. The simultaneous optimization method proposed in this study provides useful guideline for designing wastewater and heat exchanger networks with greater cost efficiencies and environmental performances.