Taxation represents a claim to statehood and plays a vital role in processes of mutual recognition between subjects and the state. Debates on the benefits of taxing the informal economy have stressed the mutual benefits of entering into such formalized contracts of recognition. However, based on eight months of ethnographic fieldwork in Eastleigh, Nairobi, I will show how fixed categories of formality and legitimacy are inadequate for capturing the empirical realities of trade and taxation in Eastleigh and beyond. Rather we need to recognize how practices of trade, taxation and governance are continuously contested and move along continuums of (in)formalization and (il)legitimization. I argue that insights into these processes lead to a broader perspective on contracts of recognition, allowing us to (a) recognize practical contracts constituted within state institutions without adhering to formalized laws and regulations and (b) question the perception of fixed links between formality and legitimacy that implicitly underlie much of the dominant development discourse on taxing the informal economy.