Abstract: To improve the accuracy of instantaneous frequency estimation for the time-varying line spectrum of unmanned underwater vehicle targets, an enhanced pseudo-Bayesian algorithm based on a Gaussian-uniform mixture model is proposed. This algorithm models the instantaneous frequency as a time-series Markov hidden variable of time-frequency spectrum magnitudes, and employs the Gaussian-uniform mixture model to uniformly quantify the uncertainties regarding instantaneous frequency, spectral spread, and noise. By combining the expectation-maximization algorithm and the Viterbi algorithm, the proposed algorithm constructs a two-stage estimation strategy under a pseudo-Bayesian framework, which not only improves estimation accuracy but also ensures noise robustness and low computational complexity. Simulation results and lake trial data demonstrate that, in typical complex underwater scenarios such as low signal-to-noise ratio, multi-line spectrum interleaving, and time-varying amplitude, the proposed algorithm achieves higher estimation accuracy and stronger noise robustness compared with conventional time-frequency ridge detection and existing pseudo-Bayesian methods. Furthermore, its computational complexity is reduced by 1 to 3 orders of magnitude in comparison with existing multi-component pseudo-Bayesian algorithm.