During the Xia and Shang Dynasties (c. 2200–1600 BC), Xuzhou lay in an area inhabited by the Dongyi or Huaiyi peoples who were constantly at war with the Shang and Zhou Dynasties. The Xuzhou region was called Huaiyang during the Zhou Dynasty (1600 BC–256 BC) since the Huai River crosses the area. During the Spring and Autumn Period (771 BC–426 BC), Xuzhou was a collection of small farming/fishing villages and towns and formed part of the border region between the Zhou vassal States of Chu, Wu and Qu. Both the States of Pi and Peng lay within its borders. Xuzhou was at one time a capital of the State of Xu, a vassal state exterminated by the State of Wu in 512 BC. In turn, Wu was conquered by the State of Yue a few decades later. Chu gradually expanded its influence around Xuzhou after absorbing the nearby State of Cai in 447 BC followed by the conquest of the State of Yue in 334 BC. By the Warring States Period, it was firmly in the cultural and administrative sphere of Chu. The State of Chu moved to this area in 278 BC after the Qin army captured its old capital, Ying, in modern Jingzhou, Hubei.
Liu Bang, first emperor of the Han Dynasty (206 BC–AD 220), was born in Pei County, Xuzhou. At the beginning of the Han Dynasty, Xuzhou became part of the Kingdom of Chu, a principality ruled by relatives of the royal Liu family. Initially, Liu Bang allowed his relatives to rule parts of the country since they were assumed to be the most trustworthy. However, the Kingdom of Chu under third generation ruler Liu Wu rebelled against the central authority during the Rebellion of the Seven Princes and was defeated. His tomb was recently excavated near Xuzhou. Historians maintain that in the ancient capital and trade center of Pengcheng (Xuzhou) one can find the "earliest reliable evidence of the presence of Buddhism in China."
After the Yellow River began to change course during the Song Dynasty (AD 960–1279), heavy silting at the Yellow River estuary