Abstract: Extended Kalman Filter (EKF) algorithm is widely used in parameter estimation for nonlinear systems. The estimation precision is sensitively dependent on EKF’s initial state covariance matrix and state noise matrix. The grid optimization method is always used to find proper initial matrix for off-line estimation. However, the grid method has the draw back being time consuming hence, coarse grid followed by a fine grid method is adopted. To further improve efficiency without the loss of estimation accuracy, we propose a genetic algorithm for the coarse grid optimization in this paper. It is recognized that the crossover rate and mutation rate are the main influencing factors for the performance of the genetic algorithm, so sensitivity experiments for these two factors are carried out and a set of genetic algorithm parameters with good adaptability were selected by testing with several gyros’ experimental data. Experimental results show that the proposed algorithm has higher efficiency and better estimation accuracy than the traversing grid algorithm.