A method for estimating the matching performance of TERCOM map under non-stationary terrain is proposed. First, the statistical property of measures of terrain matching algorithms is studied through difference process of terrain. The mean and variation of measures are expressed with regard to the moment of terrain difference. Then, the relationship between the statistical property of measures and the probability of partial searching acquisition is discussed. Estimation of TERCOM map performance with the moment of terrain difference and the probability of partial searching acquisition is proposed. Experimental results of real terrain show that the method herein is efficacious.