Originile statului Burundi se cunosc doar prin intermediul istoriei orale și al arheologiei. Există două mari legende despre apariția statului Burundi. Cea mai mediatizată vorbește despre o rwandeză pe care o chema Cambarantama și care a fondat națiunea. Cealaltă versiune, vehiculată cu precădere în perioada pre-colonială a Burundi, povestește despre Cambarantama care a venit din sudul statului Buha. Elementele constitutive rwandeze ale regatului au fost promvate de către coloniștii europeni astfel încât acestea să se potrivească vizuinii acestora conform cărora clasa conducătoare a venit dintr-o regiune cu populație hamitică din nord-vest. Aceasta teorie a continuat să fie dogma principală a statului burundez. Istoricii sunt sceptici în ceea ce privește originea hamitică a etnitei tutsi, dar încă se crede că strămoșii acestora au migrat din nord stabilindu-se în secolul XV pe teritoriul de azi al statului Burundi. Primele dovezi ale existenței unui stat Burundi datează din secolul XVI, acesta apărând pe dealurile din est. In următoarele secole acesta s-a extins, anexând regiunile mai mici intrând în competiție cu Rwanda. Cea mai mare dezvoltare a statului s-a petrecut sub conducerea lui Ntare Rugama, care a guvernat națiunea între 1796 și 1850 și a dublat teritoriul regatului.

Regatul Burundi a fost caracterizat de o autoritate politică ierarhică și de schimb economic tributar. Regele, numit mwami a condus o aristocrație princiară, (ganwa), care deținea cea mai mare parte a pământului și percepea taxe și tributuri de la fermierii locali și de la crescătorii de vite. La mijlocul secolului al XVIII-lea regalitatea tutsi și-a consolidat autoritatea asupra pământului, producției și a distribuției cu dezvoltarea ubugabire – o relație patron-client în care populația primea protecția regelui în schimbul tributului și a permanenței pe acele pământuri.

Deși exploratorii europeni și misionarii au făcut vizite scurte în regiune în anul 1856, abia în 1899 Burundi a devenit parte a Africii de Est germane. Spre deosebire de monarhia rwandeză care a decis să accepte dominația germană, regele burundez Mwzi Gisbao s-a opus influenței europene, refuzând să poarte haine după model european și a rezistat penetrării misionarilor și administratorilor veniți din Europa. Germanii au folosit forța armată pentru a se impune și deși au adus mari pagube regatului, puterea regelui a rămas intactă. În cele din urmă, germanii l-au sprijinit pe unul din ginerii regelui, Maconco, în revolta împotriva lui Gisbao. Regatele mai mici de-a lungul țărmului Lacului Victoria au fost deasemenea anexate teritoriului burundez.