Orang yang bercakap bahasa Austronesia mula tiba di Sumatera sekitar 500 SM, sebagai sebahagian daripada perluasan migrasi Austronesia dari Taiwan ke Asia Tenggara. Dengan kedudukannya dalam laluan perdagangan laut India-China, beberapa bandar-bandar perdagangan berkembang terutamanya di pantai timur Sumatera dan dipengaruhi oleh agama Hindu dan Buddha. Salah satu kerajaan yang paling awal diketahui ialah Kantoli, yang berkembang di abad ke-5 Masihi di selatan Sumatera. Kantoli digantikan oleh Kerajaan Srivijaya dan kemudian oleh Kerajaan Samudra.

Srivijaya merupakan monarki Buddha, berpusat di apa yang kini adalah bandar Palembang. Empayar ini menguasai kepulauan Melayu menerusi perdagangan dan penaklukan dari abad ke-7 hingga ke-9, serta membantu menyebarkan kebudayaan Melayu ke seluruh Sumatera, Semenanjung Melayu, dan bahagian barat Borneo. Empayar Srivijaya merupakan suatu kuasa maritim (thalassocracy) yang memperluaskan pengaruhnya dari pulau ke pulau. Palembang pada masa itu merupakan pusat pembelajaran yang termasyhur, dan ia merupakan tempat sami China Buddha I-Tsing belajar bahasa Sanskrit sebelum berlepas ke India dalam 671 Masihi. Dalam perjalanan kembalinya ke China, beliau juga menghabiskan masa selama empat tahun di Palembang untuk menterjemahkan teks agama Buddha dan menulis dua manuskrip.

Pengaruh Srivijaya berkurangan dalam abad ke-11 selepas ia ditewaskan oleh serangan empayar Chola yang ketika itu memerintah di India Selatan. Sumatera seterusnya tertakluk kepada penaklukan dari kerajaan-kerajaan di Jawa, iaitu pertama oleh Singhasari dan kemudian oleh Majapahit. Pada masa yang sama Islam masuk ke Sumatera di abad ke-6 dan ke-7 Masihi melalui saudagar Arab dan India.[6] Menjelang akhir abad ke-13, raja-raja kerajaan Samudra telah memeluk agama Islam. Ini disaksikan oleh Marco Polo yang melawat pulau ini di tahun 1292 dan oleh Ibnu Battuta yang melawat dua kali sepanjang 1345-1346. Kerajaan Samudera digantikan oleh Kesultanan Aceh yang kuat, yang kekal hingga abad ke-20.

Kedatangan Belanda telah membuat banyak negeri-negeri di pulau Sumatera secara beransur-ansur jatuh di bawah kawalan mereka, namun Kesultanan Aceh di utara pulau merupakan halangan utama, yang menyebabkan Belanda terlibat dalam Perang Aceh (1873-1903) yang lama dan mahal. Kebanyakan Sumatera jatuh di bawah kawalan kerajaan Hindia Timur Belanda, dan menjadi pengeluar utama lada, getah, dan minyak. Pada awal dan pertangahan abad ke-20, ahli akademik dan pemimpin Sumatera termasuk pada tokoh-tokoh penting dalam pergerakan kemerdekaan Indonesia.