Nur wenig ist bekannt über die erste große Einwanderungswelle nach Madagaskar, die man auf das dritte bis sechste Jahrhundert nach Christus datiert. Bei diesen ersten Besiedlern der Insel handelte es sich jedoch nicht, wie man vermuten könnte, um Afrikaner, sondern um Protomalaien (s. Malaien), deren Wurzeln ursprünglich in Süd-China lagen. Über Südostasien breiteten sich die Protomalaien im Zuge der austronesischen Expansion über einen Zeitraum von mehreren Jahrhunderten südwärts nach Polynesien und – vermutlich vom Süden der indonesischen Insel Kalimantan aus ausgehend – bis nach Madagaskar aus. Unklar ist, ob sie auf direktem Weg oder in Etappen über Indien und das afrikanische Festland Madagaskar erreichten.
Die Besiedelung Madagaskars durch Afrikaner geschah später und großteils wahrscheinlich nicht freiwillig. Die meisten wurden von arabischen Sklavenhändlern von der Ostküste des afrikanischen Kontinents nach Madagaskar verschleppt. Die Araber beherrschten bis ins 19. Jahrhundert hinein große Teile des madagassischen Außenhandels.
Madagaskar war zunächst dünn besiedelt. Erst mit zunehmender Bevölkerung bildeten sich Königreiche heraus, von denen die der Sakalava und Merina sowie der Betsileo die bedeutendsten waren.
Am 10. August 1500 sichtete der portugiesische Seefahrer Diogo Dias als erster Europäer Madagaskar und nannte die Insel São Lorenço. Später erscheint die Insel auch unter dem Namen Santa Apolonia auf den Karten der Portugiesen.