Traditional methods of instantaneous rotational speed estimation(IRSE) without tachometers have some problems of weak anti-noise, weak anti-near-orders and high calculating time. A new method based on Viterbi algorithm is proposed, and applied to estimate instantaneous speed of the rolling bearings under variable speed conditions. The Viterbi algorithm about hidden Markov model is introduced into rotating speed estimation, which is used to analyze the calculation times of cost functions in a time-frequency plane. According to the properties of Euclidean distance function, a new criterion of stopping cost function iteration is proposed. By using the new criterion, the time-frequency plane can be searched quickly to find the optimal local path. Besides, the IFE accuracy and calculating speed are also improved. The new method proposed is verified by simulation signals and experimental data. The results show that the efficiency of the new algorithm is improved significantly. By comparing with the IFE method based on peak search, the modified Viterbi-IFE method has higher accuracy and stability