Underwater localization is considered a critical technique in the Internet of Underwater Things (IoUTs). However, acquiring accurate location information is challenging due to the heterogeneous underwater environment and the hostile propagation of acoustic signals, especially when using received signal strength (RSS)-based techniques. Additionally, most current solutions rely on strict mathematical expressions, which limits their effectiveness in certain scenarios. To address these challenges, this study develops a quantum-behaved meta-heuristic algorithm, called quantum enhanced Harris hawks optimization (QEHHO), to solve the localization problem without requiring strict mathematical assumptions. The algorithm builds on the original Harris hawks optimization (HHO) by integrating four strategies into various phases to avoid local minima. The initiation phase incorporates good point set theory and quantum computing to enhance the population quality, while a random nonlinear technique is introduced in the transition phase to expand the exploration region in the early stages. A correction mechanism and exploration enhancement combining the slime mold algorithm (SMA) and quasi-oppositional learning (QOL) are further developed to find an optimal solution. Furthermore, the RSS-based Cramér–Raolower bound (CRLB) is derived to evaluate the effectiveness of QEHHO. Simulation results demonstrate the superior performance of QEHHO under various conditions compared to other state-of-the-art closed-form-expression- and meta-heuristic-based solutions.