Maji was founded around 1897 when Ras Welde Giyorgis stationed a garrison outpost of Ethiopian soldiers near the lands of the ture, a personage Garretson describes as "the most powerful and respected religious figure in the area."

Garretson explains how an administrative center for the region soon followed: "Built on a commanding hill were a fortified encampment of gibbi (the personal headquarters of the governor), a church and a market.

"[2] Richard Pankhurst records that its governor, Dejazmach Taye, amazed by the growing trade at Gambela to the west of him, during the 1920s attempted to develop exports of coffee, rubber, hides and ivory through the port town.

[1] During this period, the occupiers built roads so that vehicles could be driven to Maji and a Catholic Mission operated there which ran at least one school.

Based on figures from the Central Statistical Agency, in 2005 Maji has an estimated total population of 2,930 of whom 1,302 were males and 1,628 were females.