Historically, the Dutch entered the archipelago through their trading company called the Vereenigde Oost Indische Compagnie (VOC). The VOC first landed in Ambon in 1602, but reached Surabaya in 1617. The VOC had special privileges, namely the right of Octroi. Through this right, the VOC was able to monopolize the spice trade, form its own army, declare war, and enter into agreements with local kings or leaders.

Cornelius Speelman saw Surabaya as a strategic city with great potential as a port, so the central government made it the center of power in East Java or Gezaghebber in den Oosthoek. Development to support the needs of the VOC began with the Belvedere defense fort (now Jembatan Merah Plaza I), located west of the Kali Mas river to anticipate future threats. This fort was equipped with defensive structures, a customs office, and a shipyard for commercial activities. Additionally, Surabaya had a trading post as the center of VOC commercial activities, which became the primary focus for European settlements around the trading post. By the late 18th century, the European settlement on the eastern side of the Kali Mas River estuary was inadequate, so a new settlement was built on the western bank of the river, known as the Red Bridge (Roode Brug) area due to the red bridge connecting both sides of the river. In 1799, the VOC's prosperity came to an end due to corruption, escalating war expenses, and competition with other trading companies. After the VOC was dissolved on January 1, 1800, the territories under VOC control were administered by the “Aziatische Raad,” with Governor-General Johannes Siberg (1801-1804) succeeding Governor-General Overstraaten as the last Governor-General of the VOC.