Основание империи Мали приписывают магу Сундиате Кейте, правившему с 1230 по 1255 год. Сундиата был придворным рабом у царя народа сусу, унаследовавшего в VIII веке — когда Европа погружалась в Темные века — остатки империи Гана. Согласно легенде, Сундиата поднял армии воинов-призраков, чтобы сокрушить своих врагов, и так захватил главные территории, через которые шла торговля золотом. Эта история воспроизводится в поэме «Эпос о Сундиате», которую передавали друг другу через поколения гриоты — певцы и сказочники. Сундиату, сына одного из местных царей, в детстве выгнали из дома с подачи одной из жен его отца; он жил в изгнании при дворах других правителей. Повзрослев, он смог собрать армию, объединить несколько городов и победить сусу. Гриот по имени Джели Мамаду Койате описывает Сундиату как «парня, полного сил; руки его имели силу десяти мужчин, и его мускулы внушали страх его спутникам. Он уже тогда имел властный тон, свойственный тем, кому суждено повелевать». В эпосе описывается три источника обогащения:

Те, кто будут сеять,

Пусть сеют!

Те, кто будут торговать,

Пусть торгуют!

Те, кто будут сражаться,

Пусть с ражаются!

И с ражения избрал Сундиата!

Муса, чей род восходил к внуку сводного брата Сундиаты, взошел на трон в 1312 году. К этому моменту империя Мали была уже внушительной. Она состояла из земель королевства Ганы и территории под названием Мелле; но немногие путешественники забирались так далеко. К концу жизни Мусы его королевство стало одним из самых могущественных в мире, одолев соперничавшее государство Сонгай и распространив свою власть на знаменитые города Гао и Тимбукту.

Золото довлело над всеми аспектами жизни в Мали. Оно было мерой власти лидера и престижа его страны. Правители Мали долгие годы считали пышную демонстрацию материальных благ своим долгом; Муса же вывел это занятие на новый уровень. Но при всем своем богатстве Мали считалось захолустьем, далеким от средиземноморских и прочих центров образования и торговли. Муса так жаждал серьезного отношения к себе, что всякий раз, когда в гости прибывал некий сановник из другой страны, от него требовалось действовать в соответствии со строгим ритуалом. Аудиенции проводились под богато украшенным куполом во дворце Мусы в Ниани — ныне забытой столице империи. Там он восседал на троне из слоновой кости под шелковым навесом от солнца, увенчанным золотым орлом. Муса был при оружии из золота, в частности, при луке со стрелами. Все делалось ради того, чтобы произвести впечатление на подданных и иностранцев. По словам писателя ибн Хальдуна, самым дорогим сердцу Мусы предметом был золотой слиток необычайного веса — двадцать кантаров, или семьсот килограммов.

В центре имперского двора на возвышении стоял трон из твердого эбенового дерева. Муса никогда не говорил громко, а лишь шептал что-то своему глашатаю, который и произносил слова правителя вслух. Любого, навлекшего на себя его гнев, могла ждать жестокая смерть. Его указы требовали абсолютного послушания. Среди множества преступлений, за которые назначалась смертная казнь, было чихание в его присутствии. Исторические документы не дают представления о том, многих ли несчастных придворных ждала такая судьба. Если же нужно было чихнуть самому Мусе, все присутствующие громко били себя в грудь, чтобы заглушить этот звук. Никому не позволялось видеть его за едой — он всегда, даже во время поездок, делал это в уединении. Ауру царя-полубога следовало сохранять всегда, в любой момент.

Закон, действовавший еще со времен ганского правления, навеки определял богатства царей Мали. Он устанавливал, что все более крупные слитки золота являются неотъемлемой собственностью мансы. «Более крупные» означало больше нескольких грамм, то есть практически все, что представляло какую-то ценность. Шахтерам разрешалось оставлять себе золотой песок и стружку. Империя облагала налогом каждую унцию золота, пересекавшую ее границы, а частная купля-продажа золота в стране была под запретом и, естественно, наказывалась смертью. Все извлеченное или найденное золото следовало взвесить, упаковать и немедленно сдать в казну, что гарантировало королю стабильный и неисчерпаемый источник богатства. Вероятно, Мусе не приходило в голову, что это вымогательство. В конце концов, все и так принадлежало ему одному.

Царя одолевали все новые и новые амбиции. Каким бы богатым он ни был (размеры его состояния никто не считал), он подозревал, что его подданные могли бы приносить ему еще больше. Он заключил, что лучший способ поднять производительность, а следовательно, и свой доход — наделить управляющих золотыми шахтами определенной автономией. Это был один из первых примеров участия в прибылях как экономического стимула: Муса постановил, что они могут оставлять себе больше мелких самородков золота, главное, чтобы все остальное доставалось ему. Опыт подсказывал, что когда административные указания навязываются слишком жестко, рабочие начинают саботировать и выход продукции резко падает. Муса не совершил этой ошибки, и его тактика сработала великолепно. Ему оставалось откинуться на спинку трона и получать обильную и постоянную дань с рудников. Его сокровищница, где скапливались ресурсы для путешествия в Мекку, неуклонно пополнялась.

История о необычайном хадже мансы Мусы столетиями передавалась из уст в уста, а также в летописях. Арабские писатели и путешественники заполняли некоторые пробелы в повествовании, подробно рассказывая о людях и городах тех времен. Кое-какие записи оставались неизвестными публике много лет. Еще предстоит расшифровать тысячи рукописей, передававшиеся семьями из Мали в частные коллекции в прошлые века и обнаруженные совсем недавно. Один из самых важных рассказов составил дипломат и литератор конца XV века Махмуд Кати. Его сочинение «Тарих ал-Фатташ» сначала (в 1913 году) было переведено на французский, а потом на английский под названием «Хроника искателя знаний». Неизвестно, сам ли он закончил книгу или оставил эту задачу своим потомкам. Махмуд Кати называет мансу Мусу «Мали-кой Канкан Муса» и описывает его как «справедливого, благочестивого и набожного султана». Он пишет: «Его владения простирались от границ Мали вплоть до Сибиридугу [ныне это Сьерра-Леоне — прим. авт.], и все народы этих стран, сонгайцы и другие, подчинялись ему. Среди знаков его доблести — освобождение по одному рабу ежедневно, совершение паломничества в священный храм Господень и возведение в ходе этого паломничества великой мечети Тимбукту».

Кати во многом подтверждает устные рассказы, но предлагает и новое объяснение хаджу Мусы:

Его мать Канкан была местной женщиной, хотя некоторые говорят, что она арабского происхождения. Причину его паломничества сообщил мне, как излагается ниже, богослов Мухаммад Кума, да смилостивится над ним Господь, который запоминал традиции древних. Он говорил, что Мали-кой Канкан Муса по ошибке убил свою мать Нану Канкан. И он чувствовал глубокое сожаление и раскаяние и боялся возмездия. Чтобы искупить вину, он отдал огромные суммы денег просящим милостыню и решил всю жизнь поститься. Он спросил одного из улемов [мудрецов] своего времени, что он может сделать, чтобы искупить свое страшное преступление, и тот ответил: "Ты должен искать спасения у Пророка, да сохранит и благословит его Господь. Беги к нему, встань под его защиту и проси молить Бога о снисхождении к тебе, и Бог примет его мольбу. Таково мое мнение». Канкан Муса принял решение в тот самый день и начал собирать деньги и снаряжение, необходимые для путешествия. Он велел объявить об этом во всех частях страны.