The international legitimacy of overseas interests protection mechanisms is related not only to whether protective actions can gain the support of host countries, but also to the reputation of the home country. Legitimacy in this context refers to the level of adherence to the conception of international justice instead of specific rules. The conception of international justice is characterized by temporality, relativity, and constructivity. Temporality refers that the conception of international justice changes along with the development of time. Relativity refers to the heterogeneous conceptions of justice and the international community's different expectations for different countries on the legitimacy of overseas behaviors. Constructivity means that great powers always play a significant role in the construction of the conceptions of international justice. In the construction of the international legitimacy of overseas interests protection mechanisms, China should fully appreciate and respond to all the aforementioned properties. First, China's protection mechanisms should reflect the values of the time in order to attain moral force, fill the gap between its conception of justice and that of the host country, and choose standards that match its international identity and the amount of expected benefits when interpreting legitimacy. Besides, China's endeavor should not be restricted to the semantic interpretation of legal texts.  Efforts should be made to theorize practical experience as well as to reshape the conception of international justice.