This article from Brunei fm discusses the history of Islam in Brunei, the earliest indications of which come from the 12th century.

The golden history of Islam in Brunei
Brunei fm, 08 March 2010

It has been debated when Islam actually first arrived in Brunei. A number of relics showed that Islam could actually be practised in Brunei by the 12th century.

Amongst these were tombstones found in the various Islamic graveyards in Brunei particularly the one at Rangas which showed one with a Chinese Muslim by the name of Pu Kung Chih-mu. He was buried there in 1264. This is more than a hundred years earlier before the conversion of Awang Alak Betatas as the Islamic Sultan Muhammad Shah, the first Sultan of Brunei.