The border diplomacy which is intended as tool for gaining national interest should be built on 3 foundations. Those fondations are law, social and economic development and also institution building. This article will highlight the importance of institution building in border diplomacy. In order to manage the cross border relation with neighbour country, the government needs certain institution to holds the task. Related to our case, we will discuss about KK Sosek Malindo as the main institution which has been managing the border issues between Indonesia and Malaysia. KK Sosek Malindo routinely meets to solve several problems arise between both countries in the border. Since 1985, theyve already agreed various cooperations related to border management and border area development. Unfortunately, this institution became useless when cannot implement those agreements and contribute more because distracted by inapropriate structure of KK Sosek Malindo. This article also tend to convince that restructuritation of KK Sosek Malindo should be done in order to optimalize the function of KK Sosek Malindo for better bilateral relation and border area development.