The Gulf millennial is often lost in stories of migration, of economic transformation, and change in oil economies. Studies of labour almost entirely ignore Gulf citizens, outside passing remarks on their concentration in the public sector and weak representation in the private sector. Yet forces of inclusion and exclusion play across both national and expatriate divides in Gulf economies. This paper examines shifting notions of economic belonging and citizenship in the Sultanate of Oman. Nationals in Oman may have citizenship and permanence in the country, but are marginalised in economic production by their weak representation in the private sector. Non-nationals, though comprising the majority of private-sector workers, in many ways ‘belong’ in different sectors of the private sector yet have no political claim on permanence in the country. The divisions within these groups construct different senses of belonging and not belonging, resulting in tenuous economic citizenship. These patterns can have serious repercussions on future stability during times of economic crisis. This year protests about unemployment have again made headlines and prompted a flurry of policy announcements. Drawing from multi-year ethnographic and new survey research, this paper interrogates senses of belonging among Omani millennials. In so doing, it not only sheds light on the competing pressures in the governance of Gulf labour markets, but also contributes to scholarly understandings of economic citizenship and Gulf labour-market complexities in a globalised context.