This paper explores the nature and determinants of illegality in migrant labour markets. It conceptualises the various “spaces of (il)legality” in the employment of migrants, and explores the perceptions and functions of these spaces from the points of view of migrants, employers and the state. Our theoretical approach goes beyond the notion that illegality is “produced” by the state, and recognises the agency that some migrants and employers have vis-à-vis the state’s migration frameworks. Drawing on quantitative and qualitative interviews with East European migrants and employers in the UK, and analysis of the UK government’s policies, rhetoric and enforcement, we find that migrants, employers and the state all recognise the distinctions between different types of illegality, and their differentiated impacts. In particular, semi-compliance – which we define as the employment of migrants who are legally resident but working in violation of the employment restrictions attached to their immigration status – is a distinct and contested space of (il)legality that serves important functions. It allows employers and migrants to maximize economic benefits from employment while minimizing the threat of state sanctions for violations of immigration law. Semi-compliance exists, and is likely to persist, because it constitutes an equilibrium which, we show, serves the interests of migrants and employers and in practice is difficult for the state to control. We expect these findings for the UK to be of relevance to many other high income countries that, like the UK, consider migrants both as an important source of flexible labour and yet as subjects of immigration control whose employment needs to be closely controlled.