We consider the Distributor’s Pallet Loading Problem (DPLP), where a set of cuboid-shaped items should be packed in identical pallets, satisfying several practical requirements. In particular, each item may be arranged in multiple orientations, must maintain static stability, and may withstand a limited weight. Furthermore, the combined weight of the items in each pallet must not exceed its total weight limit. We consider first minimizing the number of used pallets, and second maximizing their average pack density. DPLPs are commonly solved by layer-building methods, which generate and stack compact layers of items. Such methods are generally successful when considering a set of fairly homogeneous items. However, we consider a setting where highly heterogeneous items must be packed, for which we develop a beam search algorithm called Tetris Beam Search (TBS). This algorithm is based on a new constructive heuristic for the DPLP called Tetris Heuristic (TH). Inspired by the dynamics of the popular game Tetris, TH fills pallets by creating compact layers when possible, and non-compact structures when necessary. We evaluate TBS on generated test instances from the literature, where it significantly outperforms other competing methods. TBS reduces the average number of open bins by 22% and increases the average pack density by 18%. Notably, these improvements are realized while achieving more than 85% savings in average computational time. Finally, we present results evaluating the proposed algorithm’s effectiveness on large real industrial instances obtained from an industrial partner.