Abstract This paper presents a new approach to heat exchanger network (HEN) design making extensive use of randomization techniques. It is exceedingly simple to implement and gives new insight into the hardness and the cost landscape underlying a given problem. At the same time, the results from our algorithm may be used as good initial solutions required by most non-linear optimization problem formulations of HEN design. Practical networks involve trade-off between a number of factors, all of which are difficult to incorporate in a single design methodology. Our approach is blind to any design heuristic and generates a sufficiently large number of networks that can be further evaluated to pick up the most suitable network depending on specific design requirements. However, the current version of the algorithm is limited to HEN synthesis problems that can be solved without stream splitting. We have experimented with the three standard literature problems and obtained results that compare well with the previously published results, which justify further research in this direction.