Cikal bakal kekuasaan Islam telah dirintis pada periode abad 1-5 H/7-8 M, tetapi semuanya tenggelam dalam hegemoni maritim Sriwijaya yang berpusat di Palembang dan kerajaan Hindu-Jawa seperti Singasari dan Majapahit di Jawa Timur. Pada periode ini pada pedagang dan Mubaligh Muslim membentuk komunitas-komunitas Islam. Mereka memperkenalkan Islam yang mengajarkan toleransi dan persamaan derajat di antara sesama, sementara ajaran Hindu-Jawa menekankan perbedaan derajat manusia. Ajaran Islam ini sangat menarik perhatian penduduk setempat. Karena itu, Islam tersebar di kepulauan Indonesia terhitung cepat, meski dengan damai.

Masuknya Islam di daerah-daerah di Indonesia tidak dalam waktu yang bersamaan. Di samping itu, keadaan politik dan sosial budaya daerah-daerah ketika didatangi Islam juga berlainan. Pada abad ke 7-10 M, kerajaan Sriwijaya meluaskan kekuasaannya ke daerah semenanjung Malaka sampai Kedah. Hal ini erat hubungannya dengan usaha penguasaan Selat Malaka yang merupakan kunci bagi pelayaran ke daerah itu sama sekali belum memperlihatkan dampak-dampak politik, karena mereka datang memang hanya untuk pelayaran dan perdagangan.

Keterlibatan orang-orang Islam dalam politik baru terlihat pada abad 9 M, ketika mereka terlibat dalam pemberontakan petani-petani Cina terhadap kekuasaan T’ang pada masa pemerintahan Kaisar Hi-Tsung (878-889 M). Akibat pemberontakan itu, kaum Muslimin banyak yang dibunuh. Sebagian lainnya lari ke Kedah, wilayah yang masuk kekuasaan Sriwijaya, bahkan ada yang di Palembang dan membuat perkampungan Muslim di sini (:Uka Tjandrasasmita, Sejarah Nasional Indonesia III [Jakarta: PN Balai Pustaka, 1984 hal. 2). Kerajaan Sriwijaya pada waktu itu memang melindungi orang-orang Muslim di wilayah kekuasannya.

Kemajuan politik dan ekonomi Sriwijaya berlangsung sampai abad 12 M. Pada akhir abad ke 12 M, kerajaan ini mulai memasuki masa kemundurannya. Untuk mempertahankan posisi ekonominya, kerajaan Sriwijaya membuat peraturan cukai yang lebih berat bagi kapal-kapal dagang yang singgah ke pelabuhan-pelabuhannya. Akan tetapi usaha ini tidak mendatangkan keuntungan bagi kerajaan, bahkan sebaliknya karena kapal-kapal dagang asing seringkali menyingkir. Kemunnduran ekonomi ini membawa dampak terhadap perkembangan politik.

Kemunduran politik dan ekonomi Sriwijaya dipercepat oleh usaha-usaha kerjaan Singosari yang sedang bangkit di Jawa. Kerjaan Jawa ini melakukan ekspansi Pamalayu tahun 1275 M dan berhasil mengalahkan kerajaan Melayu di Sumatera. Keadaan ini mendorong daerah-daerah di Selat Malaka yang dikuasai kerajaan-kerajaan Sriwijaya melepaskan diri dari kekuasaan kerajaan tersebut.

Kelemahan Sriwijaya dimanfaatkan pula oleh pedagang-pedagang Muslim untuk mendapatkan keuntungan di bidang politik dan pedagangan. Mereka mendukung daerah-daerah yang muncul dan daerah yang menyatakan diri sebagai daerah yang bercorak Islam, yaitu kerjaan Samudera Pasai di pesisir Timur Laut Aceh. Daerah ini sudah disinggahi pedagang-pedagang Muslim sejak abad ke 7 dan ke 8 M. Proses Islamisasi tentu berjala di sana sejak abad tersebut. Kerajaan Samudera Pasai dengan segera berkembang baik dalam bidang politik maupun perdagangan.

Karena kekacauan-kekacauan dalam negeri sendiri akibat perebutan kekuasaan di istana, Kerajaan Singasari, juga pelanjutnya: Majapahit, tidak mampu mengontrol daerah Melayu dan Selat Malaka dengan baik, sehingga kerajaan Samudera Pasai dan Malaka dapat berkembang dan mencapai puncak kekuasaannya hingga abad ke 16 M.

Di kerajaan Majapahit, ketika Hayam Wuruk dengan Patih Gajah Mada masih berkuasa, situasi politik pusat kerajaan memang tenang, sehingga banyak daerah di kepulauan Nusantara mengakui berada di bawah perlindungannya. Tetapi sejak Gajah Mada meninggal dunia (1364 M) dan disusul Hayam Wuruk (1389 M), situasi Majapahit kembali mengalami kegoncangan. Perebutan kekuasaan antara Wikramawhardana dan Bhre Wirabumi berlangsung lebih dari sepuluh tahun. Setelah Bhre Wirabumi meninggal, perebutan kekuasaan di kalangan istana kembali muncul dan berlarut-larut.

Pada tahun 1468 M Majapahit diserang Girindrawardhana dari Kediri. Sejak itu, kebesaran Majapahit dapat dikatakan sudah habis. Tom Pires (1512-1515 M), dalam tulisannya “Suma Oriental”, tidak lagi menyebut-nyebut nama Majapahit. Kelemahan-kelemahan yang semakin lama semakin memuncak akhirnya menyebabkan keruntuhannya.