Groote Eylandt, one of Australia’s largest islands, is situated north of Darwin in the Northern Territory. The Groote Eylandt Mining Company (GEMCO) is the island’s most prominent employer, having begun open-cut manganese mining in 1964. GEMCO’s long-term presence has led to a seemingly intractable conundrum: economically crucial for First Peoples yet accompanied by chronic socioeconomic and cultural problems. Huge disparities have emerged between the wealthy mining town of Alyangula (with over 90 per cent of its population non-First Peoples and with a predominantly fly-in-fly-out workforce) and the Angurugu and Umbakumba townships (over 90 per cent First Peoples populations). Adopting a theoretical framework of organisational legitimacy, this paper evaluates how enterprise bargaining might contribute to achieving Groote Eylandt’s First Peoples employment and broader community objectives (including health, housing, and environmental restoration). At present, GEMCO’s ‘Employer of Choice’ Indigenous employment strategy comprises three main goals: (1) establishing and maintaining a qualified mentor network; (2) implementing culturally appropriate recruitment and induction processes; and (3) maintaining training programmes that provide the necessary skills for specific jobs. Yet, despite an expansion of mining operations and associated services, First Peoples employment opportunities and participation in the townships have stagnated, while underemployment has become endemic. The paper summarises GEMCO’s Employer of Choice promises and then evaluates these promises against employment and community outcomes. It goes on to explore the possibilities of enterprise bargaining at GEMCO, illustrating how future enterprise agreements might enable the achievement of First Peoples intersecting employment and community goals.