In an era of culturally driven growth, urban identities are of central importance for the branding of cities. However, urban identities are under constant re-negotiation as cities’ populations become more diverse. In northern Scandinavia, some cities have developed on what were traditionally Indigenous lands but have failed to acknowledge the role these roots and histories have played in shaping the city’s identity. As the numbers of Indigenous people living in cities grow and they begin to assert their right to the city, the relationship between a city’s ‘majority population’ identity and its ‘Indigenous’ identity may become contested. Looking at the northern Scandinavian cities of Tromsø (Norway) and Umeå (Sweden), we study the conflicts that have arisen around the cities’ place identity. In Tromsø, the conflicts concerned joining the Sámi Administration Area. Whereas, in Umeå, the Sámi identity of the city was contested in relation to the inauguration of Umeå as European Capital of Culture 2014. Drawing on theories of place identity, social justice and the right to the city and analysing representations of place identity in the local media and public fora, we discuss the importance of change and reproduction of urban identities and power relations in the two cities. We conclude that contestation can open up space for change and challenge the city’s dominant power relations, encouraging a resurgent politics of recognition of Indigenous identities rather than a conciliatory form of settler-state recognition that (re)produces and maintains colonial relations.