This paper questions to what extent European citizenship matters for the status and rights of third country nationals (TCNs) in the EU, and how the underlying rationales of European citizenship may contribute to a rethinking of the rules of engagement and cooperation in the context of the EU common immigration policy. While the contribution of European citizenship to the inclusion of TCNs is often neglected, in fact it infiltrates the domain of immigration and nationality with logics of rights, where logics of state power otherwise prevail. This contrast of rights and power emerges in the rules on the status of TCNs deriving, respectively, from European citizenship, and from the EU and the Member States’ immigration and nationality laws; it echoes into a disconnect in the narratives, supranational and national, that develop around the interpretation of these rules; and ultimately it points to a gap in the rationales underpinning citizenship on the one hand, and immigration on the other one. To address this gap, the paper questions the implications of the right to belong across borders that European citizenship expresses in the context of free movement of EU nationals. This right to belong across borders points to a demoicratic norm of belonging based on mutual recognition. This norm offers a bridge between contrasting rules and disconnected narratives, and suggests new rationales for cooperation in the context of the common immigration policy.