Medan appeared from the mist of myth around 16th to 17th centuries, when two powers in northen Sumatra - Aceh and Deli - went to war. "Medan" is a Malay word for "battle field", the place where the fight between two contesting powers took place. It is also associated with "Medina", the Islamic city in Arabia where a peaceful and prosperous civil-society once was achieved under the reign of Prophet Muhammad.
The famous Sultan Iskandar Muda from Aceh defeated Aru kingdom in Deli Tua ("Old Deli" located southward of the present Medan) in 1612, established the Deli kingdom in 1632, and appointed Gocah Pahlawan as the first king. The second king, Marhum Kesawan was enthroned in 1669 and then moved the capital to the present location of Medan (the name "Kesawan" is originated from his name). The location of the capital of Deli kingdom was moved several times (to Pulo Brayan, then to Labuhan Deli) before finally settled down in the present location of Maimoon Palace in 1888 by the 9th ruler, Sultan Ma'mum Al Rasyid Perkasa Alamsyah.
In 1861 some Fujianese from Southern China began to settle in Labuhan Deli, some 20 km north towards the sea. Labuhan was an important port town of the Sultanate of Deli, where the Syahbandar (Port Master) office was located at the middle of the town near the main landing place or harbor. In 1891 a temple dedicated for Guanyin, Shoushan-gong was erected by Fujianese in Labuhan Deli to commemorate 30 years anniversary of the founding of the settlement. Labuhan Deli is the capital of Deli kingdom from the 4th ruler (Tuanku Panglima Pasutan, ruled from 1728 to 1761) until the 9th ruler (Sultan Ma'mum Al Rashid Perkasa Alamsyah, ruled from 1873 to 1924) before it was moved to Medan. The location of the palace was near the present site of the Sultan Mosque in Labuhan Deli.
After the war in 1612 and during period of the Labuhan Deli as the capital city, the area was deserted and became a small village. Anderson, a British Government Officer visited the place in 1823 and he noted that only about 200 people lived in Medan. In 1865, a Dutch planter, Nienhuys went into the hinterland and opened a Dutch plantation center to grow tobacco. His estate was located in the eastern bank of Deli River at the north-western side of the present Esplanade. The plantation became the propelling element for the growth of a new settlement.