Newcastle and the lower Hunter Region were traditionally occupied by the Awabakal and Worimi Aboriginal People who called the area Malubimba.
In 1801, a convict camp called King's Town (named after Governor King) was established to mine coal and cut timber. In the same year, the first shipment of coal was dispatched to Sydney. This settlement closed less than a year later.
A settlement was again attempted in 1804, as a place of secondary punishment for unruly convicts. The settlement was named Coal River, also Kingstown and then renamed Newcastle, after England's famous coal port.The name first appeared by the commission issued by Governor King on 15 March 1804 to Lieutenant Charles Menzies of the marine detachment on HMS Calcutta, then at Port Jackson, appointing him superintendent of the new settlement.