Мбужи-Майи тарихы ең құнды табиғи ресурстардың бірі — алмаздармен ажырамас байланысты. XX ғасырдың басында шағын шахтерлер кенті ретінде пайда болып, қала тез арада Конго Демократиялық Республикасының ең ірі орталықтарының біріне және өнеркәсіптік алмаз өндірудің әлемдік астанасына айналды.
Қаланың негізі 1914 жылы дәстүрлі түрде Бакванга кланына тиесілі жерлерде қаланды және бастапқыда Бакванга атын иеленді. Оның пайда болуы аймақтағы алмаздардың орасан зор кен орындарының ашылуының тікелей салдары болды. Қоныстың дамуына мұнда өз қызметкерлеріне арналған лагерь ұйымдастырған бельгиялық Société minière de Bakwanga (MIBA) тау-кен компаниясы толығымен бастамашы болды. Осылайша, қаланың қалыптасуының басты факторы оның бірегей орналасуы болды — ол әлемдегі ең ірі өнеркәсіптік алмаз кен орындарының бірінің үстінде салынды.
Жергілікті чилуба тілінен «ешкі суы» деп аударылатын қазіргі атауын қала 1966 жылы алды. Ол мал үшін маңызды суат болған Мбужи-Майи өзеніне сілтеме жасайды. Бастапқыдан-ақ экономика монобейінді және толығымен алмаз өндіру мен экспорттауға бағытталған болды. MIBA компаниясы тек шахталарды ғана емес, бүкіл қала өмірін басқарып, Мбужи-Майиді классикалық «компаниялық қалаға» айналдырды. 1960 жылдарға қарай жергілікті өндірістің үлесіне өнеркәсіптік алмаздардың әлемдік көлемінің 80%-ына дейін тиесілі болды.
Ертедегі Мбужи-Майи (ол кездегі Бакванга) MIBA-ның толық бақылауындағы жұмысшыларға арналған тұрғын кварталдарға, әкімшілік аудандарға және өндіру аймақтарына бөлінген утилитарлық сипаттағы қатаң аймақтарға бөлінген қоныс болды. Халық санының күрт өсуі 1960 жылы ел тәуелсіздік алғаннан кейін орын алды. Осы кезеңде қала луба халқының өкілдері үшін маңызды орталыққа айналды, бұл жаппай көші-қонды тудырып, оның тұрғындарының санының айтарлықтай өсуіне әкелді. Дәл солар қаланы басқа көптеген отаршылдық орталықтардан ерекшелендіріп, оның мәдени ортасының негізін қалыптастырды.