The earliest human settlement in Sabah can be traced back to 20,000–30,000 years ago along the Darvel Bay area at the Madai-Baturong caves. The state had a trading relationship with China from the 14th century AD. Sabah came under the influence of the Bruneian Empire in the 14th–15th century while the eastern part of the territory fell under the influence of Sultanate of Sulu between the 17th–18th centuries. The state was subsequently acquired by the British-based North Borneo Chartered Company in the 19th century. During World War II, Sabah was occupied by the Japanese for three years. It became a British Crown Colony in 1946. On 31 August 1963, Sabah was granted self-government by the British. Following this, Sabah became one of the founding members of the Federation of Malaysia (established on 16 September 1963) alongside Sarawak, Singapore (expelled in 1965), and the Federation of Malaya (Peninsular Malaysia or West Malaysia). The federation was opposed by neighbouring Indonesia, which led to the Indonesia–Malaysia confrontation over three years along with the threats of annexation by the Philippines, threats which continue to the present day.
The presence of Chinese junk in northern Borneo on Kinabatangan as been photographed by Martin and Osa Johnson in 1935, both the sultanates of Brunei and Sulu have been traditionally engaging trade with the dynasties of China and the arrival of Chinese junks was continued until the British colonial times.