The field of international relations and security studies is among the most dynamic and challenging aspects of politics. Relationship between states depend on various factors such as politics, economic cooperation and socio-cultural partnerships. Despite the growing interdependency between states through the means of bilateral, multilateral or regionalism, security issues have remained to play a vital role in determining their level of cooperation and coexistence. This qualitative research entitled: Indonesia-PNG Border security, underlines Indonesia and PNG’s foreign policy while addressing the impacts of Papuan separatism on the 750km border. The relationship of Indonesia and PNG has remained cordial and robust over the years, however the existence of the Papuan conflict has often threatened to destabilize mutual understandings between the parties. The findings specify that the issue of Papuan separatism is one the sensitive and complicated political and cultural problems of the modern era. The sensitivity that lies behind the Papuan separatism issue has often caused difficulties to Indonesia and PNG policy makers. Border policies are designed to obtain the state objectives; however, cultural aspects have always benefited the third party (OPM) in their existence along the border. Subsequently, the Papuan autonomy has allowed for the acknowledgment of Papuan’s cultural rights. Moreover, the Papuan separatism has managed to gain support from many external parties. The growing participation of external parties have triggered internal security concern. This study indicates that the Papuan separatism issue will remain to influence Indonesia-PNG border security in the years to come. The designing of border policies should focus and encourage more on building trust as means of overcoming misunderstanding. More cooperation between all relative authorities such as the CIQS is vital to maintain a good and favorable a relationship.