It is the core function of navigation receiver to calculating message parameters in time and accurately from navigation message. The software quality of message parameters solved isn’t identical because design is different. Also, the results of parameters are under influence of message’s quality. According to the problem, the analysis method of quality tree is introduced based on traditional quality model of data, the quality tree model of evaluating the quality of navigation message is established. The model is described by four characteristics:integrity, consistency, correctness and timeliness. Each characteristic has more sub-characteristics, and a sub-characteristic is quantified by data indexes. Further more, the software is developed which is evaluating the quality of navigation message with GPS as example. The model and the software are verified by measured data from receiver of GPS. The results show that this software could discover the unusual data of GPS message, including the imperfection, inconsistency, incorrect and timeout of the data. The result can be used to improve message parameters solver algorithm, and increase the reliability of message parameters solver software.