In regard to political aspirations shown by many Papuans and supporters and the ideal objective of mediation as a peaceful process of conflict management, this paper raises two questions: firstly, how is the likelihood of a third-party mediation to take place in Papua? Secondly, if a mediation facilitated by International actors took place in Papua, how should it be pursued? The objective of this paper is to investigate the opportunity for a third-party mediation to take place in Papua and for the problems in the region to be settled properly. This research will be guided by a synthesis of structural and social-psychological perspectives of third party mediation which emphasises not only the importance of resolving the problems but also the significance of improving communication between conflicting parties in seeking acceptable and applicable agreements. With such a perspective this research will examine how biased and facilitative mediation is able to frame the mediation and bring the low-intensity of conflict but complex problems in Papua to a sustainable peace settlement.This paper shows optimism that the problems in Papua can be settled peacefully. It also provides ground for an Internationally mediated negotiation to happen for the GoI and Papuans find peaceful settlements. Based on both theoretical ground as well as empirical observation, the protracted but low-level conflict in the region is overlapped by security and development problems. Instead of continuing the fight and allowing the problems unsettled, the parties of GoI and Papuans believed that the problems to be better settled in peace, including the possibility of third party mediated negotiation. While the Papuans, supported by other parties outside Papua, have called for the International community to facilitate negotiation or dialogue between the GoI and Papuans, the GoI is hesitant. A third party mediator that could preserve the territorial integrity of Indonesia and at the same time protect and promote the lives of Papuans is the key for a mediated negotiation take place in Papua and be successful.