가나 제국이 쇠퇴한 뒤 서아프리카에서는 여러 세력이 다투었다. 13세기 초 소소 왕국의 수망구루가 만딩고(말링케) 사람들의 땅을 지배하자, 만딩고의 왕자 순디아타 케이타가 여러 부족을 모아 맞섰다. 1235년경 키리나 전투에서 승리한 순디아타는 말리 제국의 첫 왕(만사)이 되었다.
순디아타의 생애는 주로 그리오(대대로 역사와 노래를 외워 전하는 이야기꾼)들의 서사시로 전해진다. 서사시에는 어려서 걷지 못하던 왕자가 일어서 영웅이 되는 극적인 장면이 나오지만, 모두 사실이라기보다는 전승으로 보아야 한다. 말리 사람들이 그 뒤 정한 규범이라고 전하는 ‘만덴 헌장’은 유네스코 인류 무형 유산에 올라 있다.
말리는 니제르강 상류의 비옥한 땅과 금 산지를 모두 손에 넣어 가나보다 훨씬 큰 나라가 되었다. 농업과 금, 사하라 무역이 함께 번영을 떠받쳤다. 왕들은 이슬람을 받아들였지만 전통 신앙도 함께 존중했다.