Nation-building remains a key challenge across south-west Pacific societies, including Solomon Islands, PNG, Vanuatu, and the more recently independent state of Timor-Leste. Following decolonisation in the 1970s, it was clear that welding the multiple languages and diverse cultures of the region into unified nations would be a challenge. Recent international 'state-building' efforts in the Solomon Islands and Timor-Leste have also faced difficulties, as evidenced by resurgent inter-communal violence in both states in 2006. It is important therefore that the processes of nation-building - of forming a cohesive political community, to support the development of a functional state - are better understood. This paper presents some preliminary findings of an AusAID-funded survey of attitudes to national identity and nation-building among tertiary students in PNG, Solomon Islands, Vanuatu, and Timor-Leste. The findings cast new light on the attitudes of potential future elites towards regional, ethnic, intergenerational and linguistic faultlines in the region, and the challenges of building a cohesive sense of political community and national identity.