В конце октября 1887 года Дюбуа отплыл из Голландии на Суматру. Там, на западном побережье острова, в Паданге, он и начал свою службу в больнице. На Суматре Дюбуа сразу приступил к раскопкам, уделяя им все свободное время. С помощью туземцев он обследовал все пещеры в окрестностях Паданга, но безрезультатно. Вероятно, только отсутствием опыта можно объяснить, что здесь, в тропиках, Дюбуа начал раскопки с пещер. Ведь то, что в Европе приводило к успеху, здесь оказывалось бессмысленным. В Европе древнему человеку приходилось прятаться в пещерах в холодное время года, при наступлении ледников, а во влажном и жарком климате тропиков, где не существует резкой разницы между летом и зимой, пещеры никогда не служили людям жильем.
Дюбуа копал год, второй, третий и все безрезультатно. Раскопки поглотили все его сбережения, но и самой маленькой косточки питекантропа он не обнаружил. Правда, попадалось много костей животных. К счастью, Дюбуа был не только упрям, но и терпелив - неудачи не остановили его.
Однажды Дюбуа получил с соседнего острова Ява обломки черепа, найденные неким ван Ритшотеном в каменоломне, где добывали мрамор. Обработав и соединив обломки, Дюбуа решил, что это череп австралоидного типа, но ни в коем случае не череп жителя Явы. Однако находка побудила ученого просить перевода на Яву. Его желание удовлетворили.
14 апреля 1890 года Дюбуа прибыл на Яву и немедленно начал раскопки неподалеку от Вадьяка, на южном берегу острова. Вскоре ему удалось найти обломки черепа. Но Дюбуа был хорошим анатомом и понимал, что ни этот череп, ни ранее найденный не принадлежат предкам человека. Следовательно слои, в которых они обнаружены, относятся к более позднему геологическому времени, а значит, и искать в них кости питекантропа бесполезно. Поэтому Дюбуа изменил место раскопок: сначала он перенес их к Кедунг-Брубусу, в сторону от побережья, а потом - в окрестности селения Триниль, где местные жители давно находили древние кости. Самые крупные, принадлежавшие животным с хоботом, они считали костями великанов.
Дюбуа начал копать в этом районе в августе 1891 года. К концу сухого времени года уровень воды в реке понизился, обнажив слои пород, в которых находили кости. Вскоре и Дюбуа обнаружил здесь множество костей и зубов вымерших млекопитающих. Самой интересной из первых находок был зуб третий верхний коренной, который сразу привлек внимание Дюбуа. Он принял его за коренной зуб большого шимпанзе, к тому времени на Яве уже вымершего. Спустя месяц всего в трех метрах от места, где был найден зуб, он откопал черепную крышку с сильно развитым надглазничным валиком. Однако Дюбуа все еще продолжал считать, что и это кости вымершего шимпанзе.