Borneyonun şimalında ilk dövlət qurumları b.e.ə X əsrdə meydana gəlmişdir. X—XII əsrlərdə böılgə malay imperiyasından asılı vəziyyətdə olmuşdur. XVI əsrdən XIX əsrin ortalarına kimi Byuney sultanlığının ərazisi olmuşdur. 1891-ci ildə Borneoda yerləşən ingilis və holland müstəmləkəlləri arasında sərhəd müəyyən edilir. 16 sentyabr 1963-cü ildə uzun sürən danışıqlardan sonra Federativ Malayziya elan edilir. Bruney Şərqi Malayziyaya daxil olmaqdan imtina edir. 1970-ci illərdə iki ölkə arasınmda münasibətlər pisləşoir. Bunun əsəs səbəblərindən biri Bruneydə qadağan olunmuş Bruney Xalq Partiyasının 8 üzvünün Malayziyada siyasi sığınacaq alması olur. Malayziya Bruney Xalq Partiyasının dəaliyyətini dəstəkləyir və onun öz ərazisində fəaliyyətinə icazə verirdi. 1977-ci ildə Malayziyanın baş naziri Hüseyn Onn Bruneylə münasibətləri düzəltməyi və hər şeyi yeni səhiifədən başlamağı qərara alır. 1979-cu ildə Hüseyn Onn Bruney tərəfindən kral toyuna dəvət olunur. 1981-ci ildə Bruney sultanı Hassanal Bolkiak ilk dəfə olaraq Malayziyaya səfər edir. 1980-ci illərdə Bruneyli tələbələr Malayziyada təhsil almağa başlayırla. 1984-cü ilin yanvarında Bruney və Malayziya arasında diplomatik əlaqələr qurulur. 2002-ci ilin iyulunda Malayziyanın Petronas neft şirkəti tərəfindən Sabahın sahil xətdindən 150 km aralıda iri neft yatağının aşkarlanması ilə münasibətlər yenidən korlanır. Bruney neft yataöının onun ərazisində yerləşdiyini iddia edərək ora öz hərbi-dəniz donanmasını göndərir. Bir başa hərbi toqquşmalar baş vermir. Tərəflər məsələni danışıqlar yolu ilə həll edirlər.

2003-cü ildə Bruney və Malayziya mübahisəli sularda neft və qaz hasilatını sərhədlərin demarkasiyasaına qədər dayandırmağı qərara alırlar. 2009-cu ilə qədər Limbanq şəhəri ətrafındakı sərhəd əraziləri iki ölkə arasaında ərazi mübahisəsi olaraq qalırdı. 2009-cu ilin martında iki ölkə arasında sərhəd anlaşması imzalanır. Anlaşmaya görə Bruney Libanqı Malayziya ərazisi olaraq tanıyır. 2010-cu ildə Malayziya Bruneyə iki karbohidrogen yatağını ərazi mübahisəsinin gündəmdən çıxarılması münasinbəti ilə minnətdarlıq əlaməti olaraq vermişdir.

bruney və Malayziyanı ortaq mədəni bağlar bağlayır. Əsasəndə Şərqi Malayziya Bruney imperiyasaının bir parçası olmuşdur. Uzun əsrlər boyu Bruney sultanlığı bütün Borneo adasını idarə etmişdir. 2011-ci ildə Bruneyi 61 470 malayziyalı ziyarət etmişdir. Malayziyanın Saravak və Sabah ştatları Bruneylə «Pan-Borneo» şossesi ilə birləşir.

2014-cü il məlumatına görə iki ölkə arasında ticrət dövriyyəsi 600 mln ABŞ dolları olmuşdur.