© The Author(s) 2018. This article analyses configurations of legal subjectivity, sexuality and the right to travel at the inception of international law. It commences a project on a genealogy of the legal subject of the right to travel that attends to sexuality and ultimately aims to shed light on legal subjectivity and sexuality in current refugee law and policy debates. In particular, it analyses the key early 16th-century work on the law of nations of the Spanish theologian and jurisprudent, Francisco de Vitoria, which produces Christian Europeans as full legal subjects with the right to world travel, in opposition to Native Americans, who were relegated to the position partial legal subjects with duties of hospitality. It argues that the attribution of the 'Supersins' of human sacrifice, cannibalism, bestiality and sodomy to Native Americans, in part through analogy to Spain's long-time enemies the Muslims, was crucial to this partial legal subjectivity, positioning both indigenous peoples subjected to colonization, and religious others, as marginalized outsiders to the law of nations at its crucial beginnings.