The residency took its final form in 1908 after Tamiang, a small area in the north, was transferred to Aceh[5][6][7] In 1863, the first Dutch settler, Jacobus Nienjuys, arrived and began to plant tobacco, nutmeg and coconut.

Others followed, and established plantations to grow tropical crops such as tobacco, rubber, palm oil and coffee on 1,000 hectares of land leased from the sultan of Deli.

The company established a local base in the village of Medan, and over the following three decades, transformed the sultanate into a huge commercial tobacco growing region.

By 1872, there were 15 tobacco plantations, 13 of them in Deli, and production increased so fast, that in 1883, it was ten times higher than a decade previously.

[10] By 1910, all the traditional rulers of East Sumatra had recognized Dutch authority over the areas they previously ruled over.

Medan was declared a municipality, with an advisory council, and in 1917 the same status was applied to Pematangsiantar, Binjei, Tebingtinggi and Tanjung Balai.

[12] The East Coast Residency was divided into five regions (afdeeling), which comprised or contained a total of 34 "native states", which were autonomous to a degree as follows:[13][14][15] The towns of Medan, Pematang Siantar, Tanjong Balai, Tebing Tinggi and Binjei were enclaves within the native states.

The work force on the coffee, rubber, tea and oil-palm plantations, which began to be planted in the late 1890s, was entirely ethnic Javanese.