Labuan, in northern Borneo, was ceded to Great Britain by the Sultan of Brunei in 1846. The British used the island initially as a naval base from which to counteract the activities of pirates from Brunei, and as a strategic refuelling station for steamships. However, as its lack of economic and strategic importance became evident, it passed through a number of different administrations. Initially ceded to James Brooke, British Rajah of Sarawak, it was handed over to the British North Borneo Chartered Co. in 1890, the Government of the Straits Settlements in 1907, and became part of the Colony of North Borneo after World War One. The Japanese occupied it from 1942 to 1945, re-naming it Maida Island after the Chief Commander of their forces in Borneo (General Maida was later killed in an air crash while travelling to Labuan from Bintulu). It was liberated from 10th June 1945 by Australian forces under General McArthur, returned to British rule, and became part of independent Malaysia in 1963.

Although rich in deposits of oil and petroleum, Labuan's only industry for much of the 19th century was coal mining. From 1847 to 1911 a number of British companies extracted coal from Tanjong Kubong at the north tip of the island. One of the later companies, New Central Borneo, constructed a railway line to transport the coal to Victoria Port. However, the mines were eventually closed after a series of accidents.