Background Indigenous peoples experience worse health and die at younger ages than their non-indigenous counterparts. Ethnicity data enables health services to identify inequalities experienced by minority populations and to implement and monitor services specifically targeting them. Despite significant Government intervention, Australia's Indigenous peoples, the Aboriginal and Torres Strait Islander peoples, continue to be under identified in data sets. We explored the barriers to Indigenous status identification in urban general practice in two areas in Sydney. Methods A mixed-methods multiple-site case study was used, set in urban general practice. Data collection included semi-structured interviews and self-complete questionnaires with 31 general practice staff and practitioners, interviews with three Medicare Local staff, and focus groups with the two local Aboriginal and Torres Strait Islander communities in the study areas. These data were combined with clinical record audit data and Aboriginal unannounced standardised patient visits to participating practices to determine the current barriers to Indigenous status identification in urban general practice. Results Findings can be broadly grouped into three themes: a lack of practitioner/staff understanding on the need to identify Indigenous status or that a problem with identification exists; suboptimal practice systems to identify and/or record patients' Indigenous status; and practice environments that do not promote Indigenous status identification. Conclusion Aboriginal and Torres Strait Islander peoples remain under-identified in general practice. There is a need to address the lack of practitioner and staff recognition that a problem with Indigenous status identification exists, along with entrenched attitudes and beliefs and limitations to practice software capabilities. Guidelines recommending Indigenous status identification and Aboriginal and Torres Strait Islander-specific Practice Incentive Payments have had limited impact on Indigenous status identification rates. It is likely that policy change mandating Indigenous status identification and recording in general practice will also be required.