ב-28 באוקטובר 1964 הגיע משה יגר אל סינגפור עם משפחתו. הוא שהה שם עד 1 בנובמבר, והיה עסוק בניהול שיחות עם חנן ליסאוואר, נציג חברת "אסטרקו" בסינגפור ועם אריה לוי, יועץ לענייני נוער לממשלת סינגפור מטעם המרכז לשיתוף פעולה בינלאומי. אחר כך המשיכו יגר ומשפחתו לקואלה לומפור, ותוארו היה "מנהל חברת אינטראסיה". יגר שהה במלזיה מ-19 בנובמבר 1964 עד 11 בינואר 1966. זמן קצר לאחר הגעתו, ב-4 בדצמבר 1964, הכריז ראש הממשלה רחמן כתשובה לשאלה של חבר פרלמנט מהאופוזיציה כי ארצו לא תכיר בישראל, אולם אין שתי המדינות אויבות. בתקופה זו נעשה המאמץ הישראלי הממושך ביותר לקידום יחסים דיפלומטיים בין שתי המדינות. מאמץ זה לא קרם עור וגידים משתי סיבות עיקריות:
בישיבת ממשלת מלזיה שנערכה בינואר 1966, נימק ראש הממשלה טונקו עבדול רחמן את גירוש יגר מפני ש"ניסה לחרחר ריב ולזרוע פחד בין מלזיה לעולם הערבי, והרשה לעצמו להתערב בעניינים מדיניים וגרם למבוכה על לא מאומה ביחסה עם ארצות ערב". למרות היותה של מלזיה מדינה מוסלמית, עד לכינוס ועידת המדינות הבלתי-מזדהות בקהיר באוקטובר 1964, לא היו לה יחסים הדוקים עם ארצות ערב ולא הפגינה גילויי איבה ועוינות כלפי מדינתי ישראל. עם זאת, מלזיה סירבה לקיים עם ישראל יחסים דיפלומטיים או יחסים בילטרליים. ההתדרדרות שחלה ביחסים הלא-רשמיים שנה לאחר מכן נבעה בעיקר מרצון המלזים לרכוש את אהדת הערבים במאבקה נגד אינדונזיה ומשאיפתה להתקבל לחברת מדינות העולם שלישי.
ב-21 במרץ 1966 העלה חבר הפרלמנט של מלזיה ד"ר טאן צ'י קון (Tan Chee Khoon) שאילתא לשר הפנים של מלזיה אסמאעיל עבדול רחמן , במסגרתה שאל את השר מה היו הסיבות לגירושו של יגר, והאם הדיווחים על אודות הגירוש אכן נכונים. אסמאעיל השיב שב-7 בדצמבר 1965 הוזמן משה יגר אל משרדו ובמהלך הפגישה נאמר לו שבמהלך שהותו במלזיה לא הגביל עצמו לפעילות מסחרית בלבד, אלא גילה עניין גם בנושאים מדיניים-פוליטיים, ולפיכך נתבקש לעזוב את המדינה. הוא חתם את התשובה באומרו שיגר מילא אחר הבקשה לעזוב את מלזיה עד 15 בינואר 1966 בנימוס (למעשה, יגר עזב את מלזיה עוד ב-11 בינואר), ולא הוצאה נגדו פקודת גירוש רשמית. תשובה זו הייתה מנוגדת לדברי ראש הממשלה טונקו עבדול רחמן, שטען שיגר אכן גורש משהוכרז כאישיות בלתי רצויה.
ההחרפה בגישת מלזיה לישראל.
ההחרפה בגישתה של מלזיה כלפי ישראל חלה בשנת 1965, מעט אחרי שמשה יגר גורש מקואלה לומפור והוכרז אישיות בלתי רצויה. ההחרפה נבעה כאמור בעיקר מרצונה של הממשלה המלזית לרכוש את אהדת מדינות ערב במאבק המר שניהלה נגד אינדונזיה וממאמציה להתקבל ל"משפחת" העמים האפרו-אסייתיים בעקבות ועידת המדינות הבלתי-מזדהות באוקטובר 1964. ההחרפה התבטאה בהתנכרות לדיפלומטים ישראלים מצד עמיתיהם המלזים, בסירוב להעניק אשרות שהייה לישראלים המגיעים למלזיה, ביוזמות אנטי-ישראליות מצד השלטונות המלזים, בהצהרות עוינות ותקיפות באומות המאוחדות ובארגונים בינלאומיים, ואף בגילויים אנטישמים. למשל, אם במהלך 1965 השתתפו בקורסים של המכון האפרו-אסייני ארבעה מלזים ומלזי אחד אחר בהשתלמות חינוכית, מאז 1966 לא הגיעו שום מלזים לישראל.
עניין ישראל עלה שוב בפרלמנט המלזי ב-23 באוגוסט 1966, כאשר ראש הממשלה טונקו עבדול רחמן הודיע שמלזיה לא מכירה בשום פנים ואופן במדינת ישראל. מלזיה אף תקפה את שכנתה סינגפור (אשר פרשה ממלזיה כשנה לפני כן והפכה למדינה עצמאית) על היעזרותה ביועצים ישראלים והשוותה את מעמדה של סינגפור בדרום-מזרח אסיה, כמובלעת בין אינדונזיה ומלזיה המוסלמיות, לזה של ישראל המובלעת בין מדינות ערב. באותה התקופה החלו להתפתח דיונים במשרד החוץ בירושלים על אפשרות לנקיטת צעדי-נגד ישראלים במקומות שונים בעולם כתגובה לעוינות הקיצונית של מלזיה כלפי ישראל, אך הקונצנזוס הרווח בקרב אנשי משרד החוץ היה שמלזיה אינה חשובה לישראל עוד ויש להתייחס אליה כאל מקרה קיצוני אבוד, והנושא נזנח.
בינואר 1968 הוטלו הגבלות על ימאים ישראלים שהגיעו לנמלים מלזים ונאסרה עליהם ירידה אל המזח. המסחר עם מדינת ישראל נאסר לחלוטין ב-1974, כמו גם מתן אשרות שהייה לישראלים שביקשו להגיע אל שטחי מלזיה. חמש שנים לאחר קבלת עצמאותה קיימה יחסים דיפלומטיים עם ערב הסעודית ומצרים בלבד, ואחרי 1967 גדל מספר המדינות הערביות עמן כוננה מלזיה יחסים דיפלומטיים מלאים. עד 1991 השלימה מלזיה את תהליך כינון היחסים הדיפלומטיים עם מדינות ערב ופתחה שגרירויות בכולן. חרף ההחרפה, נותרו בעינם קשרים מקוריים ומזדמנים, כמו ביקור שערך בנו של ראש הממשלה טונקו עבדול רחמן בן ה-35. הוא היה איש עסקים והגיע לישראל באוגוסט 1968 ביוזמת איש העסקים שאול אייזנברג בלווייתו, ומשום שייצג חברת עצים מלזית הקפיד להיפגש עם אנשים מתחום זה. מקרה אחר אירע בנובמבר 1969 כאשר נציגים מלזים בפדרציה האסיינית לספורט ביקשו מעמיתיהם הישראלים לתמוך במועמדות מלזיה לאירוח משחקי אסיה לשנת 1974. הם הדגישו שראש הממשלה רחמן התחייב למנוע כל אפליה שלא כפי שאירע במשחקי אסיה בג'קרטה ב-1962.
ימי מאהאטיר מוחמד (2003-1981).
גישתו של מאהאטיר מוחמד ליהדות ולציונות.
יחסי ישראל–מלזיה עברו טלטלה רצינית כאשר ד"ר מאהאטיר מוחמד נבחר לראשות הממשלה ב-1 ביולי 1981. ראש הממשלה רחמן פרש מתפקידו ב-1971 ונתמנה למזכיר הכללי של ארגון המדינות האסלאמיות. בשנים 1971–1981 כיהנו שני ראשי ממשלות - עבדול ראזאק חוסיין וחוסיין און - שלא סטו ממדיניות מלזיה כלפי ישראל, ובד בבד לא התעניינו בה במיוחד. מאהאטיר הגיע למשרד ראש ממשלת מלזיה עם משנה וסגנון שונים. הספר שחיבר ב-1969, "הדילמה המלאית" (The Malay Dilemma), מעיד על תפיסת עולמו הגזענית. את הספר חיבר בעקבות מהומות סיניות-מלאיות חמורות שהתחוללו במלזיה באותה השנה. בספרו האנטי-סיני, שטח מאהאטיר את אמונתו כי גזעים נבדלים זה מזה לא רק במוצאם האתני אלא גם במאפיינים רבים אחרים. היהודים למשל, על-פי מאהאטיר, אינם רק בעלי אף סולד, אלא בעלי הבנה אינסטינקטיבית בממון וכלכלה. עם הוצאת הספר לאור, הוא נאסר למכירה במלזיה והוביל להגליה זמנית של מאהאטיר ממפלגת השלטון "הארגון המלזי הלאומי המאוחד" (United Malays National Organisation). הגירוש ממפלגת השלטון לא החזיק מים זמן רב ואחרי שהוחזר הוא המשיך לפתח את הקריירה הפוליטית שלו עד שמונה לשר חינוך ומאוחר יותר לראש הממשלה. הוא התגלה כמוסלמי קיצוני, אנטי-ישראלי ואנטישמי, שהעניק סגנון חדש ושונה ליחסי החוץ של מלזיה בכלל ולא רק בסוגיה הישראלית, המבטא לאומנות מלזית וסלידה מן העולם המערבי.
תמיכה מלזית באש"ף.
תמיכת מלזיה בארגון לשחרור פלסטין הייתה החזקה ביותר מבין כל התמיכות להן זכה אש"ף ממדינות דרום-מזרח אסיה. ב-1969 הייתה מלזיה המדינה הראשונה באסיה שהתירה לפתוח בעיר בירתה משרד של ארגון פת"ח, שב-1974 נהפך רשמית למשרד של הארגון לשחרור פלסטין. באוגוסט 1982, אחרי שמאהאטיר מוחמד נבחר לראשות הממשלה, קיבל משרד זה של אש"ף מעמד דיפלומטי מלא. שר החוץ של מלזיה אז, גאזאלי שאפי (Ghazali Shafie) גרס שיש לדרוש הכרה דיפלומטית של ישראל באש"ף בטרם יידרש הארגון להכיר בישראל. במאי 1983 אירחה מלזיה, במימון האומות המאוחדות, ועידת פסגה שדנה בסכסוך הישראלי-פלסטיני ולוותה בתעמולה אנטי-ישראלית בכלי התקשורת המלזים. ביולי 1984 ערך יאסר ערפאת ביקור רשמי בקואלה לומפור שבמהלכו התקבל בידי היאנג די-פרטואן אגונג ונאם בפני עצרת רבת-משתתפים.
אנטישמיות ואנטי-ציונות בשנות השמונים.
תקופת כהונתו של מאהאטיר מוחמד הצטיינה בפעולות תעמולה רבות נגד מדינת ישראל, ובהתבטאויות ותקריות אנטישמיות ואנטי-ציוניות חריפות. האנטישמיות שמוחמד טיפח במלזיה הייתה מיוחדת במינה - הייתה זו אנטישמיות ללא יהודים משום שלא הייתה נוכחות משמעותית של יהודים במלזיה. ב-27 בינואר 1981 נשא מוחמד נאום בערב הסעודית וקרא להחזרת אדמותיהם של הפלסטינים בכוח פיזי מכיוון שישראל "אינה בלתי-מנוצחת". בשנים הבאות הוסיף מאהאטיר לנאום נגד ישראל בפומבי תוך שימוש במונחי נאצה במספר ארגונים בינלאומיים: העצרת הכללית של האומות המאוחדות, בוועידת המדינות הבלתי-מזדהות בניו דלהי ב-10 במרץ 1983, בוועידות של ארגון המדינות האסלאמיות ובמקומות נוספים.
ביוני 1983 יצא ראש ממשלת מלזיה בהצהרה המגנה את ישראל על "פלישתה ללבנון" (הכוונה למלחמת לבנון הראשונה) וכינה את ממשלת ישראל, שבראשה עמד אז מנחם בגין, "הממשלה הבלתי מוסרית ביותר בעולם". באוקטובר אותה השנה נערכה בוועידה השישית בנושא הבעיה הפלסטינית של "הוועידה האסלאמית בניו יורק". מלזיה השתתפה בכנס והביעה את מורת רוחה ודאגתה מכניסתה המחודשת של ישראל לאפריקה (להרחבה ראו יחסי אפריקה–ישראל) וקראה לעצור תופעה זו במידי. מלזיה הביעה את התנגדותה ל ובאפריל 1984 הכריזה כי תנתק את יחסיה הדיפלומטיים עם אי-איזו מדינה שתעביר את שגרירותה לירושלים.