印尼和马来西亚领土相连，有共同的边界。1957年印尼与马来亚联邦建交。60年代初，印尼反对马来亚联邦同新加坡、沙捞越、沙巴合并组成马来西亚，认为这是对印尼的包围，是英国殖民主义者的阴谋。1963年9月马来西亚成立后不久，印尼即与马断交。此后，两国处于敌对状态。苏哈托执政后，1966年8月两国签署关系正常化协议，1967年复交。1967年东盟成立后，两国关系日趋密切。近年来，两国关系比较平稳，领导人接触频繁，各个领域的交往不断，双方经常就地区和东盟内部问题保持联系、协调立场。1999年3月马来西亚外长赛阿密、2000年3月总理马哈蒂尔对印尼进行工作访问，双方签署了交通、能源、多媒体等8个合作谅解备忘录。1999年11月、2000年10月瓦希德总统两次访马。梅加瓦蒂接任总统后也曾于2001年8月赴马进行短暂访问。2004年1月，马来西亚总理巴达维对印尼进行就任后的首次访问，两国领导人就印尼在马劳工、反恐、边界和贸易等问题进行了磋商。巴达维建议双方在相互贸易中采用彼此货币进行结算，以减少汇率损失，加快支付速度，希望双方加快签署印尼劳工在马工作的谅解备忘录。同时建议双方建立领导人之间的热线电话