Non-Hermitian physics predicts open quantum system dynamics with unique topological features such as exceptional points and the non-Hermitian skin effect. We show that this new paradigm of topological systems can serve as probes for bulk Hamiltonian parameters with quantum-enhanced sensitivity reaching Heisenberg scaling. Such enhancement occurs close to a spectral topological phase transition, where the entire spectrum undergoes a delocalization transition. We provide an explanation for this enhanced sensitivity based on the closing of point gap, which is a genuinely non-Hermitian energy gap with no Hermitian counterpart. This establishes a direct connection between energy-gap closing and quantum enhancement in the non-Hermitian realm. Our findings are demonstrated through several paradigmatic non-Hermitian topological models in various dimensions and potential experimental implementations.