A novel strategy for the synthesis of a cost-effective flexible heat-exchange network (HEN) that involves the expected disturbance range in the source-stream temperatures and flow rates is presented. The network synthesis problem is decomposed into four main iterative steps: (1) the synthesis of a network candidate with a minimum total annual cost (TAC); (2) flexibility analysis without consideration of the area restrictions to verify whether the current network candidate is feasible within the full, expected disturbance range; (3) integer cuts to exclude disqualified network configurations, followed by step (1) again to synthesis a new network structure, (4) with consideration of the size restriction that has been ignored previously, execution of flexibility analysis of the network qualified in step (2), with an increase of the area of individual exchange units if necessary. A few iterations of these design steps may be required to secure the desirable results. In addition to the theoretical derivation, a numerical example is provided to demonstrate the efficiency of the proposed strategy for the synthesis of a flexible heat exchange network.