Малайя была всегда тесно связана со всем островным миром Юго-Восточной Азии – достаточно напомнить, что его подчас называют Малайским архипелагом. Похоже на то, что в глубокой древности именно через Малайю на архипелаг проникли многие компоненты, составившие затем основу населения Индонезии, и прежде всего основной малайский компонент. Ранние протогосударства в Индонезии появились, как и практически во всей Юго-Восточной Азии, примерно на рубеже нашей эры, может быть, чуть позже, чем на континенте, в IV—V вв. Это были индуистское Тарума и буддистское Калинга на Яве, буддистское Гэин на Суматре, индуистское Варунадвипа на Калимантане. И названия, и религиозно-культурная ориентация ранних индонезийских государств, даже локализация их преимущественно в западных районах архипелага – убедительное свидетельство той огромной роли внешних влияний в процессе их генезиса, о которой уже не раз говорилось применительно ко всей Юго-Восточной Азии. В отдельных случаях древние надписи фиксируют даже существование в ранних индонезийских государствах каст по индийскому стандарту. А правитель Тарумы сопоставлялся в текстах с индийским Вишну.
Структурно государства были примерно однотипны. Существовали верховный правитель-вождь, его наместники и помощники, а также производители-общинники, платившие ренту-налог в казну. Возможно, что некоторые из государственных образований были типологически близки к малайским городам-государствам, возникавшим вокруг торговых портов. В идеологии и культуре господствовали индуизм, преимущественно в шиваистской форме, хотя встречались и вишнуисты, а также буддизм. Преобладала санскритская письменность. Индо-буддийским было монументальное храмовое искусство с срответствующей архитектурой и скульптурой.
Исторически наиболее развитыми и ранее других достигшими уровня цивилизации и государственности были тесно связанные между собой Суматра и Ява, географически представлявшие как бы единую узкую полосу островов, тянущихся с северо-запада на юго-восток. Первым крупным государством на Суматре была Шривиджайя, просуществовавшая с VII по XIII в. В пору своего расцвета власть правителей Шривиджайи простиралась не только на всю Суматру, но также и на часть соседних мелких островов, временами и на часть Малакки. Шривиджайя была признанным центром мировой торговли, и именно через нее в островной мир Индонезии активно проникал буддизм. Впрочем, стоит заметить, что в самой Шривиджайе правители были достаточно равнодушны к буддизму: во всяком случае, там не обнаружено остатков таких величественных буддийских храмов и иных строений, как на Яве.
Яванское государство Матарам, основатель которого Санджайя был индуистом-шиваитом, возникло в VIII в., но уже при внуке Санджайи, основавшем династию Шайлевдров, религиозная ориентация государства изменилась. Яванские Шайлендры стали активно поддерживать буддизм махаянистского толка, свидетельством чего является величественный храмовый комплекс Боробудур. Возможно, буддийская ориентация Шайлендров сыграла определенную роль в том, что в начале IX в. один из представителей этой династии с помощью династического брака стал правителем Шривиджайи и основателем там той же династии Шайлендров – факт, внесший немалую путаницу в загадку истории индонезийских государств. Что же касается Матарама, то это яванское государство было типично восточным по его внутренней организации. Землей в ней распоряжался сам правитель, административный аппарат состоял из служивших ему чиновников. Общинные крестьяне вносили в казну ренту-налог, за счет редистрибуции которой содержались знать, воины, чиновники, духовенство. Немалую роль в стране играли торговые города-порты и вообще торговля и торговые операции.
Матарамские Шайлендры сошли с исторической арены в XI в., уступив место государству, созданному одним из приближенных последнего правителя, его зятем Эрлангти (Эрланга). Эрлангти восстановил на Яве приоритет шиваизма, но не преследовал буддистов. Напротив, стремился создать некий синтез обеих религий. Его государство подчинило себе почти всю Яву и являло собой строго централизованную организацию с хорошо налаженной чиновной администрацией, развитыми ремеслом и торговлей. Государство заботилось о поддержании в порядке ирригационной сети и упорядочило налогообложение. Размер ренты-налога составлял примерно десятую долю урожая.