The Romani peoples have consistently been associated with magic and fortune-telling, yet surprisingly little is known about how the association first developed. This article provides a systematic and critical assessment of the earliest known documentary evidence for Romani magical practice, considering all known sources from two formative periods: the middle to late Byzantine period (ca. 1050–1453) and the first decade of the northwest-European diaspora (1417–1427). The article argues that associations with magic first emerged through a process of stereotype transfer and appropriation in the Byzantine context, by which older images of oriental magic practitioners and heretics were transferred to and performed by an emerging ethnic group. In the northwest-European context, palmistry was a popular Romani service but also became a source of rumor and suspicion when interactions broke down. The article argues that the magical exchange has been a central site for the construction of ethnic boundaries between Roma and non-Roma.