Heat exchanger network (HEN) synthesis is a topic of high importance, encompassing several solution approaches and problem aspects. One such aspect crucial to industrial applications is flexibility, since real systems often experience variations of certain parameters, e.g., inlet temperatures or flowrates. Decades of research have revealed numerous methods for analyzing the flexibility of a given heat exchanger network. Meanwhile, the synthesis of flexible HENs continued to prove to be a severely difficult task, especially since handling the parameter deviations should not compromise the high level of heat integration. This work introduces a novel direction for synthesizing flexible HENs by combining flexibility analysis methods with P-graph-based, exhaustive, combinatorial network generation. The method generates all feasible networks that satisfy both the structural criteria and the maximum energy recovery over the entire variation region, and presents them ordered by capital cost. This first iteration of the work focuses on variations in inlet stream temperatures. This allows proving the validity of the underlying concepts by generating HENs that achieve minimum utility consumption for the entire range of temperature variations. The capability to generate multiple suitable networks is demonstrated through a case study, where 429 feasible networks were generated, which are all capable of achieving maximum heat integration within the parameter variation region. For the best generated design options, a 4–6% increase in capital cost compared to the base case is sufficient to satisfy the flexibility requirements.