James Brooke was appointed the White Rajah of Sarawak ( now known as Kuching ) by the Bruneian Empire in 1841 . In 1861 , the Sultanate of Brunei ceded the Bintulu region to Brooke . Bintulu was a small settlement at that time . A wooden fort named Fort Keppel was built in the village , named after Sir Henry Keppel , who was a close friend of the Rajah James and Charles Brooke . Sir Henry Keppel was responsible for crushing the Dayak piracy in the Saribas between 1840 and 1850 . Meanwhile , Charles Brooke was a nephew of James Brooke and would later become the latter 's successor as the second Rajah of Sarawak . Odoardo Beccari , an Italian botanist , visited Bintulu in 1867 . On 4 August , he started his journey on a gunboat named " Heartsease " , which was to send $ 6 @,@ 000 to Brunei for concessions being made to James Brooke in the Mukah and Bintulu regions . He went to Labuan before coming back to Bintulu . He dropped off at Kemena River on 13 August 1867 . His observations of the village were recorded as follows :