Gaining legitimacy in their host country environment is a key priority for multinational corporations’ public relations efforts since it secures their local social license to operate. By applying neo-institutional public relations to corporate diplomacy, this paper argued that institutional linkages between corporations and local government could enhance the building of legitimacy. The study sought to determine whether institutional relations affect the perception of organizational legitimacy, focusing on the United Arab Emirates. In non-democratic countries, public relations tends to be perceived as less sophisticated, and legitimacy becomes even more critical for foreign corporations. Therefore, a one-factorial (corporate diplomacy with/ without governmental involvement) between-subjects experimental design study surveying a representative sample of residents in the United Arab Emirates (N = 199) was conducted. The results imply that corporate diplomacy with governmental linkages leads to a higher perception of moral, pragmatic, and regulative organizational legitimacy, partially mediated by media credibility, governmental legitimacy, and issue legitimacy.