Дипломатические отношения между СССР и Малайзией установлены 3 апреля 1967 года. Малайзия заявила о признании Российской Федерации в качестве страны-преемника Советского Союза 31 декабря 1991 г.
Действует ряд межправительственных соглашений и меморандумов о взаимопонимании, в т. ч. об экономическом сотрудничестве, о сотрудничестве в области обороны и оборонных технологий.
Налажен политический диалог, осуществляется регулярный обмен посланиями на высшем уровне и между руководителями внешнеполитических ведомств.
В мае 1997 г. Верховный глава (король) Малайзии Туанку Джаафар посетил Санкт-Петербург с неофициальным визитом.
Премьер-министры Малайзии посещали Москву в 1972, 1979, 1987 и 2002 г. Нынешний глава кабинета Махатхир Мохамад, кроме того, в августе 1999 г. побывал с рабочей поездкой в Хабаровске и Улан-Удэ. В ноябре 2000 г. и октябре 2001 г. на саммитах АТЭС в Брунее и Шанхае состоялись неформальные встречи В.В.Путина и Махатхира.
Председатель Правительства России находился в Куала-Лумпуре в 1998 г.Ф для участия в саммите АТЭС и провел переговоры с руководителем малайзийского кабинета. В 2002 г. на саммите АТЭС в Мексике состоялась встреча главы российского правительства и вице-премьера Малайзии.
Неоднократно Малайзию посещали заместители Председателя Правительства (1985, 1994 и 2000 гг.).
Активно взаимодействуют наши внешнеполитические ведомства: их руководители регулярно обмениваются официальными визитами, осуществляют двусторонние контакты на международных форумах. В соответствии с Протоколом 1987 г. МИД двух стран периодически проводят консультации на уровне заместителей министров.
С 1995 г. в штатах Пинанг, Кедах и Перлис действует Почетный консул России.
Поддерживаются межпарламентские связи: делегации Госдумы и Совета Федерации посещали Малайзию в 1994, 1999 и 2002 годах, в 2003 г. они приняли участие в проходившем в Куала-Лумпуре XI заседании Азиатско-тихоокеанского парламентского форума; спикер палаты представителей малайзийского парламента нанес официальный визит в Москву в 1991 г., в 2003 г. в России побывала делегация малайзийских сенаторов.
Установлены контакты между высшими судебными органами двух стран: Председатель Верховного Суда России В.М.Лебедев посетил Малайзию в апреле 2001 г., ответный визит Председателя Федерального суда Малайзии Мохамеда Дзаиддина Абдуллы состоялся в июне 2001 г.