The politics and trade in Southeast Asia since the 7th century had seen the early rise of Brunei as an important port in Borneo. When the Malacca fell to the Portuguese in 1511, Islam spread to northern Borneo.  Brunei grew as a new, powerful Islamic sultanate; European traders stopped by its port as they bought spices in the Moluccas. Friendships and conflicts of interest between the two powers were exacerbated by the issue of Christianization and Islamization. In the 16th century the conflicts forced Brunei to defend and expand its territory from North Borneo to the Philippines. This article discusses the Sultanate of Brunei‘s early growth in the 15th and 16th Centuries particularly related to the political context of religion and trade in Southeast Asian waters.  The article presents reasons why their initial encounters with Europeans, especially the Portuguese and Spaniards, were important not only for Brunei’s dynamic history, but also for the establishment of its Islamic and Malay identities in later periods.