The history of Sabah can be traced back to about 23–30,000 years ago when evidence suggests the earliest human settlement in the region existed. The history is interwoven with the history of Brunei and the history of Malaysia, which Sabah was previously part of and is currently part of respectively. The earliest recorded history of Sabah being part of any organised civilisation began in the early 15th century during the thriving era of the Sultanate of Brunei. Prior to this, early inhabitants of the land lived in predominantly tribal societies, although such tribal societies had continued to exist until the 1900s. The eastern part of Sabah was ceded to the Sultan of Sulu by the Sultan of Brunei in 1658 for the former helping a victory over Brunei enemies, but many sources stated it had not