As the grid frequency is difficult to be accurately measured, a new method of employing the filter function of the adaptive notch filter structure and the characteristics of the fundamental and harmonic of the voltage signal is proposed in this paper. The square value of output of the notch filter is used as the cost function and the online iterative algorithm of the notch parameter is deduced according to the stochastic optimization theory. Thus, the frequency-dependent notch parameter is adaptively adjusted, and the grid frequency estimation can be achieved. The method is simple, and the convergence rate and the approximation precision of the proposed algorithm are verified by simulation and experimental test. The results show that the frequency of power system can be accurately obtained by the proposed estimation method.