The primary problem in this study is how the decision-making authority for border cooperation with the District Government of Nunukan should get prior approval of the Central Government? Second, what kind of border cooperation that have been undertaken by the Indonesia-Malaysia of North Kalimantan Nunukan Regency to Tawau City of Sabah State? This study uses a normative approach. The results of this study concluded that first, the decision to border cooperation is still dependent on the approval of the Central Government since Regional Authority of Nunukan Regency is very limited. Second, the border cooperation that have been undertaken by the Indonesia-Malaysia of North Borneo Nunukan to Tawau City State of Sabah is the cooperation of the Socio-Economic of Malindo families. However, it does not create an interface connection with the regional development programs and regional economic cooperation such as BIMP-EAGA, which is actually very relevant to be integratively and complementatively developed with the Socio-Economic of Malindo families.