Background: The global rise of Type 2 diabetes and its complications has drawn attention to the burden of non-communicable diseases on populations undergoing epidemiological transition. The life course approach of a birth cohort has the potential to increase our understanding of the development of these chronic diseases. In 1987 we sought to establish an Australian Indigenous birth cohort to be used as a resource for descriptive and analytical studies with particular attention on non-communicable diseases. The focus of this report is the methodology of recruiting and following-up an Aboriginal birth cohort of mobile subjects belonging to diverse cultural and language groups living in a large sparsely populated area in the Top End of the Northern Territory of Australia. Methods: A prospective longitudinal study of Aboriginal singletons born at the Royal Darwin Hospital 1987-1990, with second wave cross-sectional follow-up examination of subjects 1998-2001 in over 70 different locations. A multiphase protocol was used to locate and collect data on 686 subjects with different approaches for urban and rural children. Manual chart audits, faxes to remote communities, death registries and a full time subject locator with past experience of Aboriginal communities were all used. Discussion: The successful recruitment of 686 Indigenous subjects followed up 14 years later with vital status determined for 95% of subjects and examination of 86% shows an Indigenous birth cohort can be established in an environment with geographic, cultural and climatic challenges. The high rates of recruitment and follow up indicate there were effective strategies of follow-up in a supportive population.