A methodology for sampling homeless populations in inner Melbourne was developed to study their health status and prevalence of tuberculosis. This paper describes the design, development and implementation of the project. The results of health status and tuberculosis analysis are published elsewhere. Involvement and interaction with local service providers and agencies to homeless people was central to the project throughout. A definitional construct of homelessness was developed, drawn from local and overseas literature and contemporary local experience. The study's aim was to obtain a representative sample of homeless individuals in various levels of accommodation and a convenience sample of those who were unaccommodated (streets and parks). A comprehensive sampling frame of accommodation options was constructed from available databases, and systematic sampling applied to produce a sample of 396 beds, from which 284 participants were enrolled. Convenience sampling of unaccommodated homeless individuals produced 100 participants. All agreed to undergo a comprehensive questionnaire, blood and Mantoux testing, the latter being completed successfully in 94%. Commonsense, cultural sensitivity and a non-threatening approach were critical to the success of the project and the security of the field workers. The methods described attempt to address recognised difficulties of sampling from homeless populations and should be reproducible both in the future and elsewhere. Potential for selection bias remains the main threat to validity, which the described methodology combined with adequate resources should help to address.