The relations between the two countries can be traced back on the 15th century, with many Hadhrami people playing an important role during the Islamization of the Malays people. This also proved with the current culture of Malaysian Muslim in the present day resembles an Arab culture.
Currently, both countries in the process to enhance bilateral trades. In 2013, the bilateral trade stood over U$200 million with the major import from Yemen such as seafood products, coffee, honey, leather and fruits while the export from Malaysia are the cooking oil which Malaysia consider as the biggest producers and exporters to Yemen and also to the Middle East. Both countries also has signed a joint commission and promote bilateral relations in higher education.