בשנות ה-60 חל מפנה ביחסה של מלזיה לישראל אחרי שנעשו ניסיונות רבים לכונן יחסים דיפלומטיים בין שתי המדינות ונרשמו מגעים בלתי-פורמליים בין ישראל למלזיה. ניסיון בולט היה שליחותו של משה יגר, איש שירות החוץ הישראלי, לקואלה לומפור במסווה של איש עסקים. בראשית 1966 גורש יגר ממלזיה ולאחר מכן החלה החרפה בגישת מלזיה לישראל: סירוב להעניק אשרות שהייה לישראלים שביקשו לבקר במלזיה, גילוי התבטאויות אנטי-ישראליות בארגונים בינלאומיים, הטלת מגבלות על ספנים ישראלים שהגיעו לנמלים מלזים ועוד. החרפה זו הגיעה לשיא עם היבחרו של מאהאטיר מוחמד ב-1981 לראשות ממשלת מלזיה. עם זאת, הסכמי אוסלו והתקדמות תהליך השלום הישראלי-פלסטיני הובילו להפשרה בגישה הנוקשה של מלזיה כלפי ישראל, הפשרה שלא החזיקה מים מכורח היותו של מוחמד מוסלמי קיצוני, אנטי-ישראלי ואנטישמי, שהעניק סגנון חדש ושונה ליחסי החוץ של מלזיה בכלל ולא רק בסוגיה הישראלית. הוא נותר בשלטון עד 2003, ושב אליו ב-2018 בגיל 93.
אחרי שמוחמד ירד מהשלטון במלזיה בראשית העשור הראשון של המאה ה-21, ההתבטאויות האנטי-ישראליות והאנטישמיות נרגעו יחסית, אך אי-קיום יחסים בילטרליים בין שתי המדינות נותרו בעינו. כאשר מאהאטיר מוחמד שב לשלטון ב-2018, הוא חזר להשמיע את דעותיו האנטי-ישראליות, אנטישמיות והאנטי-ציוניות בפומבי. כינון יחסים בין ישראל למלזיה נראים בלתי אפשריים בעקבות האנטישמיות השלטונית השוררת במלזיה, ובשל תפיסת משרד החוץ בירושלים שסוגיית מלזיה אינה חשובה ליחסי החוץ של ישראל.
מלזיה לא עוררה עניין רב אצל מעצבי מדיניות החוץ של ישראל וגם לא בקרב פקידי משרד החוץ שעסקו בענייני אסיה, חרף הפרובוקציות הרבות שעוררה, בייחוד מאז עלייתו של מאהאטיר לשלטון. משה שרת היה חריג, ואף פעל לשם כינון יחסים דיפלומטיים בין שתי המדינות, ללא הועיל. גם גולדה מאיר גילתה עניין מה, במיוחד אחרי שהניסיון לשגר נציג ישראלי לא-רשמי ב-1965 לא עלה יפה. ראשי הממשלות ושרי החוץ שבאו אחריהם גילו אדישות והתעלמו ממלזיה אף על פי שמדינה זו הייתה פגיעה לפעולות תגמול שניתן היה להפעיל כנגדה בארצות הברית: למשל, העמדות האנטישמיות החוזרות ונשנות של מאהאטיר יכלו לשמש עילה לפעולה מתאימה בארצות הברית. ראש הממשלה יצחק רבין גילה עניין כלשהו במלזיה ב-1994 במסגרת פעילותו באינדונזיה ותפישתו כי נוצרה שעת כושר לקדם ולנסות מיסוד יחסים בילטרליים עם המדינות המוסלמיות באסיה בעקבות התפתחויות במזרח התיכון והשינויים בעולם בכלל, אלא שפעולה זו לא הייתה נמרצת דיה.
יחסים לא רשמיים עם פדרציית מלאיה.
טרם קבלת העצמאות מהבריטים.
ניסיונות להקמת נציגות דיפלומטית ישראלית בקואלה לומפור.
בתכנון הראשוני של הקמת נציגויות דיפלומטיות ישראליות במדינות אסיה לא הומלץ על פתיחת נציגות במלאיה, מאחר שב-1949 הייתה מלאיה נתונה תחת שלטון האימפריה הבריטית והייתה לקולוניה. יתר על כן, הרעיון בדבר עצמאות מלאית טרם הועלה. גם על פתיחת קונסוליה לא הומלץ דבר, אלא אם יהיה אינטרס כלכלי לעשות כן. המצב השתנה בראשית שנות ה-50 של המאה ה-20, כאשר החלו ההכנות למתן עצמאות לחצי האי המלאי. כאמור, ישראל הכירה בעצמאותה של מלאיה, אך הדבר לא הוביל לקשירת קשרים דיפלומטיים. ראש ממשלתה הראשון, טונקו עבדול רחמן , גילה יחס חיובי כלפי ישראל ואף שקל להכיר בה באורח רשמי, אולם הלחץ של האסלאם הרדיקלי מבית ושל מדינות ערב מחוץ הביאו לידי כך שהאהדה הזו תישאר כמס שפתיים.
הפגישה המדינית הראשונה שהתקיימה בין שתי המדינות התרחשה בעת ביקורו של שר החוץ וראש ממשלת ישראל לשעבר משה שרת בקואלה לומפור, במסגרת מסעו באסיה ב-1956. מנהיג מלאיה היה כאמור טונקו עבדול רחמן, שכיהן באותה השנה כ"שר ראשי" (Chief Minister) והיה מועמד לכהן כראש ממשלה לכשתתקבל עצמאותה של מלאיה שנה לאחר מכן, ב-1957. שרת נועד עם רחמן ב-14 באוקטובר 1956. השניים ניהלו שיחה ובמהלכה הציע שרת למנות קונסול כללי ישראלי בקואלה לומפור ועם בוא עצמאותה של מלאיה יועלה הדרג הייצוגי מקונסולרי לדיפלומטי. שרת טען שתגובתו של רחמן הייתה "חיובית ללא היסוס", והבהיר שהאחרון מקדם את העניין "בברכה". לעומתו טען רחמן כי אישור הרעיון היה מותנה בהחלטת משרד החוץ וחבר העמים של הממלכה המאוחדת, שהיה אחראי על ניהול מדיניות החוץ של מלאיה עד שנת עצמאותה. לפני פרידתם חזר רחמן ואישר את הסכמתו למינוי קונסול ואמר: "לכבוד ייחשב לנו לקבל אצלנו נציג של ישראל".
חודשים אחדים חלפו ביעף, וב-13 בפברואר 1957 הותרה מחלקת אסיה ואפריקה (מאס"ף) במשרד החוץ שבירושלים לשגרירות ישראל בלונדון לפנות אל משרד החוץ הבריטי ולבקש ממנו אישור לפתיחת הקונסוליה. הבריטים שאלו על כך את המלאים, אך הללו לא מיהרו להחזיר תשובה. דומה היה כי נטייתם שלילית, על אף גילויי הרצון הטוב של רחמן. ב-26 ביוני 1957 נפגש שר החוץ שרת עם מנכ"ל משרד החוץ ולטר איתן, מנהל מחלקת אסיה דניאל לוין וסגנו של האחרון, אלישיב בן חורין והתרעם על הזנחת הטיפול בפתיחת הקונסוליה בקואלה לומפור. שרת סבר כי מאז שיחותיו האחרונות עם רחמן נרקמה והתגבשה קנוניה נגד ישראל בקואלה לומפור. נוסף על כך, שרת האמין כי מלחמת סיני (שפרצה שבועיים לאחר תום מסעו באסיה) הייתה בין הגורמים שהניאו את המלאים מהסכמה לפתיחת נציגות דיפלומטית ישראלית בבירתם.
ב-13 באוגוסט 1957 הודיע משרד החוץ הבריטי לשגרירות ישראל בלונדון כי תשובת המלאים טרם נמסרה וייעץ לסגל השגרירות להמתין זמן מועט עד ה-31 באוגוסט (מועד קבלת העצמאות של מלאיה) ואז לחדש את הבקשה ולהגישה במישרין אל ממשלתו החוקית של רחמן. ב-26 באוגוסט אותה השנה שלח ראש ממשלת ישראל, דוד בן-גוריון, איגרת ברכה לעמיתו המלאי רחמן ובה כתב ש"ישראל מוכנה לפתוח בארצו נציגות הולמת". יתר על כן, ישראל הצביעה בעד צירופה של מלאיה אל האומות המאוחדות. בהיעדר תשובה לאגרת של בן-גוריון, הנחה משרד החוץ לנציגויות ישראל באו"ם ובסידני שבאוסטרליה לברר אצל עמיתיהם המלאים מהי עמדת ממשלתם בנוגע לפתיחת הקונסוליה.
מלאיה העצמאית.
ניסיונות נשנים לכינון יחסים דיפלומטיים.
ב-12 בדצמבר 1957 הצהיר ראש ממשלת מלאיה רחמן בפני חברי הפרלמנט המלאי: בד בבד, הבהיר רחמן כי אין לפרש את דבריו אלו כי בעקבות הכרת ישראל במלאיה תהא חייבת ארצו לקשור עמה קשרים דיפלומטיים. ההידברות עם מלאיה נותרה תקועה עד אשר ב-27 באוגוסט 1959, סיפר מחמד סופי (Sopiee), מבכירי הדיפולמטים במשלחת המלאית אל האומות המאוחדות, לבן-שיחו הישראלי כי "התחזקות המפלגות הדתיות במלאיה הסירה לעת עתה כל אפשרות להקמת יחסים דיפלומטיים עם ישראל".
ב-10 בנובמבר 1959 דיווח ציר ישראל בסידני, משה יובל, שנפגש קודם לכן עם רחמן בעת שזה האחרון ערך ביקור באוסטרליה. עבדול רחמן אמר ליובל: "הנני זוכר את שיחתי עם מר שרת. הנהגת מלאיה מודעת היטב לאופיה של ישראל, אך ההמונים המוסלמים בארצנו מתנגדים לקשירת קשרים עם ישראל. לכן אין אנו יכולים למסד עמכם יחסים מכל סוג שהם". עם קבלת דיווח זה, הבריק אלישיב בן חורין ב-19 בנובמבר ליובל הנחיה שלשונה:
ברם, ההנחיה התקבלה לאחר שרחמן עזב את אוסטרליה ובינתיים דאג להבטיח לערבים שמלאיה לא תקשור יחסים דיפלומטיים עם ישראל ודבריו אלו התפרסמו בעיתונות בירדן. בפריז, כמו גם בכמה בירות אחרות בעולם, התקיימו יחסים אישיים בין שגרירי ישראל ואלו של מלאיה. ב-20 ביוני 1960 שלח שגריר מלאיה בצרפת, טונקו איסמאעיל בן טונקו יחיא, מכתב לשגריר ישראל בצרפת, ולטר איתן, ובו הסביר שלא ניתן לכונן יחסים דיפלומטיים "בגלל הקשיים הנוכחיים של הממשלה הנובעים ממחסור בכוח אדם מאומן וקשיים אחרים בכינון נציגויות מחוץ למלאיה. שגריר ישראל בבנגקוק, מרדכי קדרון, ביקר בקואלה לומפור בחודשים מרץ-אפריל 1960, אם כי לא הצליח לשוחח עם רחמן.
כינוס קונפדרציית הכדורגל של אסיה.
באוגוסט 1960 חלה תפנית בניסיונות ההידברות עם מלאיה. באותו החודש נקרתה הזדמנות חדשה להעברת מסר לממשלתו של רחמן. היה זה לרגל כינוס קונפדרציית הכדורגל של אסיה שישראל הייתה חברה בה (עד לגירושה ב-1978), וראש הממשלה עבדול רחמן היה נשיאה. ההתאחדות לכדורגל בישראל לא יכלה לשלוח נציג מטעמה אל הכינוס וביקשה ממשרד החוץ לשגר לקואלה לומפור דיפלומט מאחת השגרירויות הסמוכות. במשרד החוץ בירושלים הוחלט לשלוח לכינוס את משה יגר, שכיהן באותן השנים כמזכיר שני בשגרירות ישראל בראנגון. יגר הגיע לקואלה לומפור ב-4 באוגוסט 1960 אחר הצהריים. עם נחיתתו בנמל התעופה הבינלאומי של קואלה לומפור נתקבל יגר על ידי התאחדות הכדורגל במלזיה ואת יומו הראשון הקדיש להיכרות עם נציגי המדינות האחרות שהגיעו לכינוס. למחרת בואו, ב-5 באוגוסט, הוזמן לביתו של פ. פ. נאראיאנאן (P. P. Narayanan), המזכיר הכללי של האיגוד הלאומי של פועלי המטעים, שנחשב לידיד ישראל. נאראיאנאן המליץ ליגר לשלוח עיתונאי מקומי לישראל שיסקר את החיים בישראל ויתעדם, על מנת ליצור מודעות לישראל בקרב הציבור המלאי. הוא גם סבר כי אין באפשרות מלאיה לכונן יחסים דיפלומטיים עם ישראל על אף העובדה שהקנאות המוסלמית אינה אמיתית, ואף על פי שכוחה של המפלגה האסלאמית הפאן-מלאית (PMIP) אינו ניכר בפרלמנט.