The city-state of Melaka (Anglicized form is Malacca) was founded in approx. 1400 by a Hindu prince named Parameswara; however, he (or his descendants) later converted to Islam, theorized due to the influenced of Arab traders. Malacca soon grew to be a bustling trading port due to its location, and at its peak it sent tribute to China and Siam.

Unfortunately, Malacca fell to the Portuguese in 1511, and the fleeing royal family established the various royal houses in modern-day Malaysia.

Would this fit your criteria?