Schon vor etwa 8 000 Jahren lebten in diesem Gebiet Khoisan als Sammler und Kleintierjäger. Im 2. Jh. n. Chr. erreichten die Bantuwanderungen das Territorium des heutigen Staates, ab dem 8. Jh. gründeten Araber und Perser an der Küste Handelsniederlassungen. Als Vasco da Gama 1498 die Küste von Mosambik erreichte, war Sofala