This work proposes a novel approach for the simultaneous synthesis of Heat Exchanger Networks (HEN) and Utility Systems. Given a set of hot and cold process streams and a set of available utility systems (e.g., gas turbine, steam cycle, boiler, etc), the method determines the optimal selection of utility systems, their arrangement and design (including steam generator), and the heat exchanger network (between process-process as well as process-utility and utility-utility streams) rigorously considering the trade-off between efficiency and capital costs. The mathematical model is formulated as a Mixed Integer NonLinear Program (MINLP) and it combines the SYNHEAT superstructure for HENs with ad hoc models/superstructures for utility systems. The challenging MINLP is solved with a two-level algorithm using at the upper level the Variable Neighbourhood Search (VNS) algorithm to optimize the integer variables, and at the lower level the SQP algorithm to optimize the real variables. The algorithm is tested on problems with up to 15 streams (corresponding to 465 binary variables).