Heat integration by means of Heat Exchanger Network (HEN) synthesis is fundamental in Process Engineering. There are aspects and design options that so far have been scarcely explored in this area. That is the case of heat and work integration. Recent literature shows that the simultaneous optimization of HEN with pressure recovery units can yield substantial gains. Superstructure based mathematical models for HEN synthesis are usually extended for dealing with heat and work integration formulations. Those models are complex to solve, containing nonlinearities and non-convexities that need to be overcome with simplifying assumptions (e.g., isothermal mixing after stream splitting or limiting the structural possibilities) and efficient solution approaches. An important trend in the heat integration literature is the use of meta-heuristic methods. These have arisen as an interesting alternative to the deterministic approaches. Meta-heuristics are attractive since they do not require advanced derivative-based concepts and can treat objective functions as “black-boxes”. Those strategies have been used for solving several industrial problems, including HEN synthesis. Promising solutions have been achieved in several benchmark case studies, often with formulations less simplified than those used when deterministic solvers are employed. This work aimed to fill a literature gap by applying a meta-heuristic approach to an enhanced stage-wise superstructure for HEN synthesis extended to handle streams with pressure recovery. The aforementioned superstructure-based model comprises more options than usually found in the literature, such as utilities allocation prior to units that perform heat exchange between two process streams. For achieving its goal, the model entailed several new variables related to pressure recovery, which had to be included to the meta-heuristic scheme. In order to test the methodology, it was applied to a case study taken from the literature. The strategy here used was able to outperform the solution previously reported in the literature, demonstrating that meta-heuristics can be efficiently applied to a heat/work integration model derived from a superstructure more complex than that employed in previous investigations.