Za to Dajakowie, plemiona zamieszkujące wnętrze Borneo, nie byli pod kontrolą Brunei.
Po upadku Malakki na Malajach aktywnie działali Portugalczycy, którzy od 1530 roku prowadzili regularny handel z Brunei i opisywali jego stolicę, jako otoczoną kamiennym murem. Najstarsze zachodnie informacje o Brunei pochodzą z zapisów Włocha, Ludovico de Varthema. Podczas rejsu na Moluki wylądował on na Borneo i spotkał się z mieszkańcami Brunei. Jego zapisy sięgają do 1550 roku.
W czasie gdy Brunei rządził piąty sułtan Bolkiah, państwo panowało nad nadmorskimi obszarami północno-zachodniego Borneo (obecnie Brunei, Sarawak i Sabah) i sięgało po Seludong (obecnie Manila), archipelag Sulu i części wyspy Mindanao. W XVI wieku wpływy sułtanatu Brunei rozciągały się po deltę rzeki Kapuas w zachodnim Borneo. Malajski sułtanat Sambas w zachodnim Borneo i sułtanat Sulu na południu Filipin weszły w związki dynastyczne z domem panującym Brunei. Inni malajscy sułtani, rządzący krajami Pontianak, Samarinda i Banjar, uznawali sułtana Brunei za pierwszego wśród nich. Prawdziwa natura relacji Brunei z innymi malajskimi państwami wybrzeży Borneo i archipelagu Sulu pozostaje przedmiotem badań – nie wiadomo, czy poszczególne państwa były jego wasalami, tworzyły sojusz, czy luźny związek.