This paper explores the relationship between two of the most common legal concepts in European migration and nationality laws: legal residence and physical presence. While the contemporary citizenship debate often assumes that citizenship is awarded to persons who have a ‘genuine link’ to the state awarding citizenship, our study interrogates this assumption by studying what is required of applicants in terms of legal residence and physical presence. We do so by studying the law as well as the practice of the law’s application. Our study reveals that not all naturalization schemes require legal residence and that many schemes do not require (extensive) physical presence. Moreover, the disconnect between legal residence and physical presence is often quite substantial. First, while legal residence is a requirement to be met for persons who seek to obtain citizenship through ordinary naturalisation procedures, it is not for many who can obtain citizenship through preferential naturalisation—often the most popular method of naturalising in the EU. Second, legal residence does not coincide with physical presence, either in EU law or in national law. When required, the duration of physical presence is always shorter than that of legal residence, often considerably shorter, or, not infrequently, absent altogether. Third, national authorities often do not examine whether applicants for naturalisation meet the physical presence requirements and indeed cannot easily examine this in a Union where internal borders have largely disappeared.