Die Geschichte der Mayeyi lässt sich bis ins Jahr 200 zurückverfolgen. Bis 305 sollen sie aus dem Kongo in ihr heutiges Siedlungsgebiet gezogen sein.[2] Sie siedelten in der Umgebung von Linyanti, zogen aber unter König Hankuze Mitte des 18. Jahrhunderts ins Okavango-Delta (heute in Botswana), ehe sie in den Caprivizipfel nach Linyanti und Sangwali zurückkehrten.[3]