This paper explores the ‘puzzle of the nomads’ in the Metaphysics of Morals: the apparent tension between Kant’s argument about the duty to leave the state of nature and his insistence that European colonizers cannot permissibly force nomads to enter a civil union. Arguing that the puzzle is twofold, I suggest that the answer lies in the relationship between the state and territory in Kant’s work. After showing the shortcomings of an approach which suggests that nomadic peoples cannot enter the civil state without settling, I defend an alternative interpretation, which conceives the territoriality of the state as contingent.