Bukti awal kedatangan dan penyebaran Islam di Nusantara bergantung kepada batu nisan dan bukti-bukti lain yang bertaburan di rantau ini.
Contoh penting termasuk batu nisan yang ditemui di Champa sekitar awal abad ke 11M, batu nisan di Gresik, Jawa bertarikh akhir abad ke-11M dan Batu Bersurat Terengganu bertarikh 1303, rekod penempatan orang Islam di Majapahit dan kumpulan pedagang Islam di utara Tanah Melayu, serta pengislaman raja Pasai pada tahun 1282.
Pada akhir abad ke-15, Islam sudah mengukuhkan kedudukan di Tanah Melayu, Sumatera, bahagian utara Pulau Jawa, Brunei dan Utara Borneo. Islam juga menembusi Maluku dan Sulu
Teori Kedatangan Islam di Nusantara
Tidak ada jawapan yang tepat bagi memastikan siapakah yang pertama sekali menyebarkan Islam di Nusantara kerana tiada bukti sahih yang ditemui bagi memastikan bilakah tarikh kedatangan mereka dan golongan manakah yang terlebih dahulu menyebarkan Islam.Walau bagaimanapun, dengan berpandukan beberapa penemuan batu bersurat dan catatan sejarah yang dibaca, ahli-ahli sejarawan tempatan telah membuat pelbagai teori kedatangan Islam ke Nusantara . Berikut adalah teori yang dikatakan ahli sejarawan tempatan.
Teori Kedatangan Islam Secara Langsung Dari Tanah Arab
Berdasarkan catatan sejarah Cina yang menyebut bahawa pada abad ke-7 Masihi, orang-orang Arab telah sampai ke Tanah Jawa.Pada tahun 684, mereka telah mendirikan sebuah perkampungan di pantai barat Pulau Sumatera.Menurut satu catatan lagi, pada zaman pemerintahan khalifah Al-Makmun bin Harun Ar-Rashid, seorang nakhoda telah memimpin seramai 100 orang mubaligh dengan 1 orang dari kalangan mereka berketurunan Quraish belayar menuju ke Nusantara untuk menyebarkan Islam. Apabila mereka sampai di Perlak, mereka mengadap Raja Perlak, Acheh dan berjaya mengislamkan baginda.Baginda Raja Perlak mengahwinkan puterinya itu denagan mubaligh Quraish itu tadi sementara mubaligh lain berkahwin dengan wanita biasa. Hasl perkahwinan mubaligh Quraish dengan puteri raja tersebut,Allah kurniakan mereka seorang putera lalu diberi nama Syed Abdul Aziz yang kemudian menjadi Sultan Perlak.
Terdapat juga dalam satu catatan Barat menyebut bahawa pada tahun 1717 Masihi, sebuah angkatan laut Islam yang terdiri dari 35 buah kapal berlayar dari Tanah Arab menuju ke China. Dalam perjalanan ke China,kapa-kapal itu telah berhenti sebentar di Ceyloon di Sri Lanka, Srivijaya dan Palembang.Ketika mereka berhenti , mereka telah berdakwah dan menyebarkan agama Islam di situ.
Teori Kedatangan Islam Melalui India
Hubungan India dengan beberapa negara di Nusantara telah lama terjalin.Pada abad ke-13 Masihi, apabila kerajaan umat Islam di Arab menguasai bahagian barat dan timur India, mereka menjadikan Gujerat sebagai pangkalan penting bukan sahaja sebagai pelabuhan, bahkan sebagai pusat perhubungan antara timur dengan barat.Dengan adanya kemudahan tersebut, saudagar-saudaugar Muslim dari Gujerat dikatakan sering berkunjung ke Nusantara untuk berdagang dan sekaligus menyebarkan ajaran Islam kepada penduduk tempatan. Ada pendapat menyatakan kedatangan Islam ke Nusantara ialah melalui daerah Bengal yang terletak di Malabar, India bukan Gujerat.
Bengal jatuh ke tangan umat Islam pada abad ke-13 Masihi lalu dijadikan pusat pengajian dan penyebaran ajaran Islam terulung di India. Ramai pelajar yang lulus di pusat pengajian tersebut merantau ke Nusantara untuk mengembangkan ajaran Islam bermazhab Syafie.Ramai daripada mereka berkahwin dengan wanita tempatan lalu menjadikan rumah mereka sebagai tempat mengaji Quran dan fardhu ain.
Teori Kedatangan Islam Melalui China
Islam telah sampai ke Tanah Besar China sejak zaman Khalifah Uthman bin Affan lagi. Baginda telah menghantar bapa saudara Rasulullah SAW yang bernama Saad bin Abi Waqas ke sana untuk menyebarkan agama Islam di negara China yang luas itu.Pada zaman pemerintahan Bani Umaiyyah, Khalifah Al-Walid telah menghantar pasukan tenteranya ke sempadan Negeri China. Ketua pasukan tentera tersebut telah menghadap raja China dan berunding dengannya. Menurut catatan Cina, pada abad ke-9, ramai penduduk di sebelah selatan negara China khususnya Yunan,China telah memeluk Islam.
Pada suatu masa, berlaku huru hara di daerah Yunan tersebut, lalu ramai Muslim berhijrah ke Asia Tenggara. Antara mereka ada yang menetap di Champa,Kemboja dan ada juga yang menetap di Negeri Pantai Timur Tanah Melayu.Oleh sebab itulah,sesetengah seni bina masjid lama di Kelantan dan Demak,Indonesia mempunyai senibina Cina.
Sesetengah ahli sejarawan tempatan berpendapat kedatangan Islam ke Nusantara melalui China telah berlaku pada akhir abad ke-10 dengan awal abad ke-11.
Penyebaran Islam sebelum kebangkitan Melaka
Sebelum kebangkitan Melaka, Islam terbatas di pelabuhan-pelabuhan di Sumatera. Bukti kehadiran Islam di kawasan pelabuhan-pelabuhan ini termasuk catatan pada 1292 oleh Marco Polo mengenai negeri-negeri Pasai dan Perlak yang mempunyai pemerintah-pemerintah Islam, dan batu nisan seorang raja Pasai yang meninggal dunia pada tahun 1297 yang mempunyai nama Islam Malek-al-Salleh.Penduduk di sekitar pelabuhan-pelabuhan ini adalah antara yang paling awal dalam Asia Tenggara memeluk Islam. Sebab pemelukan Islam awal ini termasuk jarak kawasan ini yang jauh daripada pengaruh kerajaan Hindu Majapahit, dan hubungan dagang yang lama antara kawasan ini ada dengan pedagang-pedagang India yang telah memeluk Islam.