Accurate health information is a key component in the development of health improvement strategies. This paper provides a discussion of the challenges in improving hospital information systems in relation to indigenous patients. Based on interviews with both staff and patients of a major city hospital complex, a picture emerges of the need for bottom-up approaches to understanding perceptions of identity. Indigenous patients were found to be generally comfortable about identifying themselves on hospital records (if asked), but were often not clear why such questions were asked. On the other hand hospital staff were often uncomfortable about asking and were equally not always clear why such information was needed. Issues of accurate hospital record administration are discussed in relation to the attitudes and perceptions of both staff and patients.