This paper explores how the concepts of ‘citizenship’ and ‘belonging’ are taking shape in urban Africa. As a study of insiders and outsiders, of intimate strangers and the politics of citizenship and autochthony, the paper discusses the tensions and possibilities of encounters between f lexibly mobile Africans and bounded state-driven citizenship regimes. Centred on the pervasive ambivalence of cities as cosmopolitan places and spaces of uncertainties, the paper explores and interrogates the limits of citizenship – its root in the nation-state and its discursive embodiment in particular notions of rights which represent the framework for urban inclusion and exclusion (Isin et al. 2008; Isin 2012). Often isolated from the rights and privileges of the included or of those who ‘belong’, ‘outsiders’ tend to mediate barriers, borders and boundaries in f luid and dynamic ways, producing identities that run across cultures, languages, spaces and places in cities and national contexts. The efforts and processes they engineer at ‘composite’ or ‘frontier’ identities (Kopytoff 1987; Warnier 2007; 2012; Nyamnjoh 2011) often escape scholarship that uncritically reproduces taken-for-granted dichotomies and bounded notions of being and belonging (Gupta and Ferguson 1992, 1997; Geschiere 2009; Isin 2012).