Malaysia's approach to foreign relations over seven decades has been in some ways both creative and distinctive. This article focusses on how Malaysian foreign policy has been influenced by the heritage of inter-state relations among the Muslim monarchies (sultanates, kerajaan) of the Malay Archipelago in the pre-colonial period. Taking note of current research on China's foreign-policy traditions, the article examines Malay literature and letters with the aim of identifying key principles and values operating in the four centuries preceding the consolidation of the British and Dutch colonial domination in the 1800s. It asks how the state was constituted in Malay thinking, and what the Malay writings reveal about the drivers operating in inter-state relations. Particular attention is given to the style of relationship-building, and the way the monarchies responded to hierarchical relations, especially involving "rising powers". An insistence on non-interference in the domestic affairs of others is also noted-as is a persistent aspiration toward what might be termed "moral balance". The article seeks to throw light on Malaysia's present-day approach to China-which is receiving much international attention-as well as its long-term support, in ASEAN and other contexts, for a strongly organic concept of regionalism.