AbstractHigh‐utility itemset (HUI) mining is an important tasks during data mining. Recently, many algorithms have been proposed to discover HUIs. Most of the algorithms work only for itemsets with positive utility values. However, in the real world, items are found with both positive and negative utility values. To address this issue, we propose an algorithm named Efficient High‐utility Itemsets mining with Negative utility (EHIN) to find all HUIs with negative utility. EHIN utilises 2 new upper bounds for pruning, named revised subtree and revised local utility. To reduce dataset scans, the proposed algorithm uses transaction merging and dataset projection techniques. An array‐based utility‐counting technique is also utilised to calculate upper‐bound efficiently. EHIN utilises various properties and pruning strategies to mine HUIs with negative utility. The experimental results show that the proposed algorithm is 28 times faster, and it consumes up to 10 times less memory than the state‐of‐the‐art algorithm FHN. Moreover, a key advantage is that EHIN always performs better for dense datasets.