مالزى با اندونزى وجوه اشتراک فراوانى در زمينه‌هاى فرهنگى اعم از زبان، مذهب و اخلاق دارد. به رغم اين نزديکى فرهنگى روابط خصمانه‌اى طى سال‌هاى ۶۵ - ۱۹۶۳ بين دو کشور ايجاد شد که مهمترين مسئله منطقه را به‌وجود آورد. اين خصومت آشکارا از اوايل ۱۹۵۷ شروع شد و شايد ريشه آن شرايط سياسى متفاوتى بود که دو کشور در آن آزادى و استقلال خود را کسسب نمودند. مالزى که قبلاً مستعمره انگلستان بود، از طريق مذاکرات صلح‌آميز با آن کشور به استقلال رسيد. ولى اندونزى از طريق کوشش‌هاى نظامى در مقابل هلندى‌ها (استعمارگران مجمع‌الجزاير اندونزي) کسب استقلال نمود. مالزى به‌خاطر حفظ روابط حسنه با انگلستان به‌صورت يکى از اعضاء جامعه مشترک‌المنافع باقى ماند و در سياست خارجى نيز طرفدارى و وابستگى به غرب را ادامه داد، و در صحنه داخلى نيز سيستم ظاهرى دموکراسى پارلمانى و سرمايه‌گذارى آزاد را دنبال نمود. ولى دولت اندونزى سياست خارجى ضديت با غرب را اتخاذ نمود و از برقرارى سيستم پارلمانى نيز پرهيز کرد و سيستم سرمايه‌گذارى آزاد را هم نپذيرفت. در ۱۹۵۷ مالزى از قضيه ادعاى اندونزى نسبت به ايزيان غربى (گينه نو غربي) دفاع نکرد و در ۱۹۵۸ دولت مالزى به شورشيان سوماترائى که عليه حکومت اندونزى اقداماتى کرده بودند پناهندگى داد و موجبات خشم آن دولت را فراهم آورد.


دولت اندونزى هم در پاسخ، عبور کشتى‌هاى مالزيائى را از تنگه مالاکا محدود نمود و به اذيت و آزاد ملايوهاى مقيم اندونزى پرداخت. بالاخره در ۱۹۵۹ دو کشور يک قرارداد دوستى امضاء نمودند. ولى عدم اعتماد متقابل سبب شد که ايجاد روابط دوستانه و همکارى مشکل باشد. پيشنهاد تنکوعبدالرحمن در ۱۹۶۱ مبنى بر ايجاد فدراسيون مالايا، سنگاپور و سه دولت بورنئو (يعنى بروني، صباح و ساراواک) در جاکارتا با سردى روبه‌رو شد. در ۱۹۶۲ اندونزى با ايجاد فدراسيونى در شمال بورنئو که پايگاه نظامى خارجى باشد مخالفت کرد؛ و وقتى فدراسيون مالزى عاقبت‌الامر در ۱۹۶۳ تشکيل شد عبدالرحمن تصميم دولت خود را مبنى بر باقى ماندن پايگاه‌هاى نظامى انگلستان در فدراسيون جديد اعلام نمود. دولت اندونزي، مالزى را آلت دست قدرت‌هاى استعمارى غرب در جنوب شرقى آسيا دانست. سوکارنو رئيس‌جمهور اندونزى سياست مقابله را پيش گرفت. بالاخره اين تحولات سبب شد که ترتيبات منطقه‌اى (Maphilindo)، مرکب از کشورهاى مالزي، فيليپين و اندونزى (که در اوت ۱۹۶۳ در مانيل مورد موافقت قرار گرفته بود) از ميان برود و روابط ديپلماتيک بين دو کشور قطع شود.


در ماه سپتامبر همان سال نيروى دريائى اندونزى به کشتى‌هاى تجارى و کشتى‌هاى نيروى دريائى مالزى حمله کردند و چريک‌هاى اندونزى به دهکده‌هاى صباح و ساراواک هجوم بردند. ولى در ژانويه ۱۹۶۴ با ميانجيگرى ايالات متحده آمريکا آتش‌بس اعلام شد. مجدداً از اواسط ۱۹۶۴ با مخالفت اندونزى از عقب‌نشينى از ساراواک روابط خصمانه بين دو کشور از سر گرفته شد. بالاخره با وقوع کودتاى نافرجام کمونيستى سپتامبر ۱۹۶۵ در اندونزى و متعاقب آن برکنارى سوکارنو و قدرت گرفتن سوهارتو، خصومت بين دو کشور فروکش نمود. با به قدرت رسيدن سوهارتو در مارس ۱۹۶۶ روابط بين دو کشور بهبود يافت. سه ماه بعد از اين تاريخ نمايندگان دو کشور در بانکوک با يکديگر ملاقات نموده و در مورد بهبود روابط دو کشور مذاکراتى را صورت دادند. با امضاء موافقت‌نامه عادى شدن روابط در اوت ۱۹۶۶ روابط دو کشور بهبود يافت. در مارس ۱۹۶۷ روابط تجارى و بازرگانى دوباره برقرار گرديد. دو کشور موافقت کردند براى مقابله با دزدى دريائى در تنگه مالاکا با يکديگر همکارى نمايد، و از فعاليت عناصر کمونيست در بورنئو ممانعت به عمل آورند. به هر حال روابط ديپلماتيک کامل در اوت ۱۹۶۷ دوباره برقرار شد و در مارس ۱۹۶۸ دو کشور طى صدور بيانيه مشترکى اعلام نمودند که در آينده تمام اختلافات خود را از طريق صلح‌آميز حل و فصل نمايند. در مورد مرزهاى دو کشور در طول ۶۰۰ مايل تنگه مالاکا منعقد گرديد. (هر دو کشور ۱۲ مايل دريائى را براى حدود آب‌هاى سرزمينى خود تعيين کرده‌اند. ولى عرض تنگه مالاکا در بعضى قسمت‌ها کمتر از ۲۴ مايل مى‌باشد. لذا در نظر گرفتن حدود آب‌هاى سرزمين ۱۲ مايل براى هرکدام از دو کشور غيرممکن است).


در مارس ۱۹۷۲ دو کشور قدم فراتر گذارده و اعلام نمودند که کشتى‌هاى جنگى خارجى (غير از دوکشور) بايد براى عبور از تنگه مالاکا قبلاً اجازه لازم را کسب نمايند، و براى حفاظت و حراست محيط زيست تانکرهائى که ظرفيت‌ آنها بيش از ۲۰۰ هزار تن باشد حق عبور ندارند. نمونه ديگر همکارى‌هاى دوجانبه، امضاء قرارداد استرداد مجرمين در ۱۹۷۴ و اجراء آن در اوت ۱۹۷۵ مى‌باشد. اين دو کشور مسلمان که هر دو سياست گرايش به غرب دارند به‌خصوص بعد از حمله ويتنام به کامبوج (اوايل ۱۹۷۹) روابط گسترده‌ترى را به‌طور متقابل و نيز در چارچوب اتحاديه آسه‌آن دنبال کرده‌اند.