In the 4th century, the ruler of this region was Raja Surcup, who had managed a boundary wall around his city. This fort was well known after the name of Raja Sarcup, a cruel and cunning ruler. Later the founded city was named after Kharal chief, Khan Kamal Khan Kharal, in the 14th Century and was, historically, known as "Kot Kamalia". During the Indian Rebellion of 1857, it was one of the sites of an uprising by the local people, who held it for a week. In 1901, Kamalia had a population of 6,976. Kamalia was historically part of the erstwhile district and tehsil of Montgomery (Sahiwal), Punjab. According to Cunningham, it was one of the towns taken by Alexander the Great in 325 BC.