The community known today as the Sri Lankan Malays traces its roots to political exiles, convicts, servants and soldiers sent to colonial Ceylon by the Dutch East India Company from the late 17th to the late 18th century and by the British after their takeover of the island in 1796. These ancestors of today's community came from diverse linguistic, cultural and class backgrounds across the Indonesian archipelago and, to a lesser extent, the Malay Peninsula. Among the early exiles, for example, were kings and princes from south Sulawesi, Madura and Java, while soldiers in the early 19th century were recruited mostly from villages on the Peninsula. This variegated group was not always known as 'Malays.' Drawing on archival sources, memoires and interviews this article attempts to trace the history of Sri Lankan Malay nomenclature by exploring how members of the group referred to themselves, how others (in the colonial and postcolonial periods) have referred to them, and how 'insider' and 'outsider' perceptions of the community interact and impact shifting naming practices and, with them, shifting identities.