The preference of states to use public diplomacy strategy to support the realization of their national interests has become an international phenomenon nowadays. Public diplomacy in the modern era of International Relations turns out to be an instrument for states to exercise their soft power, as well as to convey specific messages intended for the international public. Thus, public diplomacy could be an alternative way for states that had serious barriers in practicing formal diplomacy in conventional ways. Palestine, as an entity whose legal status remains debatable, also utilizes public diplomacy as its strategy to gain support and recognition from the international community. This paper would aim to answer the research question on how Palestine exercises its public diplomacy, particularly digital diplomacy and citizen diplomacy, to gain international recognition for its statehood. By means of the use of social media and the exposure on Palestine’s internationally well-known figure, Palestine is building a perception that Palestine itself is a state with no difference with the other states — therefore deserves independence and total sovereignty over its territory.