荷兰东印度公司首先把目标定在印度尼西亚。印度尼西亚位于亚洲东南部，地跨赤道，由太平洋与印度洋之间的3000多个大小岛屿组成，是世界上最大的群岛国家，有“千岛之国”之称。17世纪人口300万左右，土地面积有190余万平方公里，是个多民族的国家。印度尼西亚当时处于分裂状态，分布着许多小国家。荷兰人到来时，印度尼西亚已被葡萄牙控制，但16世纪葡萄牙日渐衰落，荷兰趁机排挤葡萄牙人的势力。在征服印度尼西亚的过程中，荷兰人多次发动战争，进行武力征服，建立殖民统治。1603年，荷兰在爪哇建商站。1605年，征服盛产香料的马鲁古(即摩鹿加)群岛中的安汶岛、帝利岛。1606年又独占班达岛的香料贸易，此时公司规模已很大，有武装舰船41艘、商船3000艘，雇员达10万多人。1619年，荷兰攻占爪哇岛上的雅加达，自此以后，荷兰就把它作为侵略印度尼西亚的中心据点。

    起先荷兰东印度公司有意识地试图避免获得领土属地，因阿姆斯特丹的理论家和政治家把葡萄牙的势力在东方的衰落归结于它将力量和资本消耗在领土征服上，警告荷兰东印度公司不要重犯类似错误。公司开始是以巩固自己的贸易垄断、创造条件以便在尽可能低廉的价格下取得当地的货物为自己的主要任务，当地人的生命、福利就顾不上考虑了。

   公司在开始进入印度尼西亚时，是采用谈判和订立协定的方式，以便公司代理人按照市价收购货物，包括奴隶。例如17世纪东印度公司与峇厘以及其他岛的统治者缔结关于供应奴隶的协定，让土著王公们成为主要的奴隶贩卖人。最后在其绝对垄断权确立后，便按照任意规定的低廉价格来收购货物。公司走完这一过程所用的时间的长短，取决于当地统治者力量的强弱。在摩鹿加群岛上，公司在极短的时间内走完了这一过程。至于其他强大的王国，东印度公司则不得不极小心地利用其封建国家内部矛盾和部落间的战争，以便公司确立对这些地区的统治，尤其在爪哇更加特别小心谨慎，因为爪哇岛上的一些王国不愿与公司妥协�倍�且还力图把荷兰赶出岛屿去。

    1652年荷属东印度公司与马打兰苏丹订立协定，根据这一协定，马打兰承认了公司在爪哇的领地权，公司的领地与马打兰以多罗磨河(或译为兰大隆河)为界。但在南边，荷兰领地的边界则没有划定。在这一时期内，公司还没有能力征服马打兰。这样，东印度公司便采取供应它在爪哇领地所需要的粮食，以此来拉拢马打兰。

    1674年马打兰国内爆发起义，苏丹苏苏胡南在起义者占领了首都之后逃到东印度公司的领地中，表示愿意用任何代价来换取公司的帮助。苏苏胡南死后，其子阿孟古辣二世于1677年与公司订立协定，阿孟古辣二世承认给予东印度公司在马打兰全部领土上进行无限制贸易的权利，割让加拉横和勃艮安地区给公司；承认以沿南安由河直至其流入印度洋之处为公司领地的边界；割让爪哇北岸的三宝拢城给公司；给予公司在南旺建立造船厂的权利；偿付公司因给予军事援助而耗费的全部费用；在偿付相应款额之前，将马打兰全部海港交由公司支配。1677年的协定给荷兰东印度公司在印度尼西亚的进一步扩张创造了绝对有利的条件。协定签订以后，1678年公司将荷兰军队开入马打兰，镇压起义军。1680年起义完全被镇压下去。

    1751年，马打兰发生了反荷兰的起义。起义者很快就控制了马打兰的大部分地区，威胁到公司的领地，连荷军统帅也在战斗中被击毙。但很快在起义者中，曼古·布米和曼古·涅哥罗为了王位发生内讧。公司抓住这一机遇，分别与曼古·布米和曼古·涅哥罗进行谈判。经过谈判后，公司于1755年把马打兰分裂为日惹和梭罗两个附属于荷兰的封建小国，对其实行分而治之。