BACKGROUND: The Expanded Program for Immunization (EPI) random walk method has been widely used by the World Health Organization and others for rapid cluster sample surveys where an up-to-date household sampling frame is not available. However, it is not a probability sample, does not allow for population movement since the last census, and does not ensure objectivity in household selection or permit call-backs for non-response. Compact segment sampling avoids these problems and has been proposed as a slower but cleaner alternative. METHODS: We conducted two surveys, one using the EPI scheme and one using compact segment sampling, to estimate vaccination coverage in Western Region of The Gambia within 3 months of each other in 2000-2001. RESULTS: Point estimates for vaccination coverage from the two surveys rarely differed by more than 2%. Any differences were more likely to be due to household selection than to population movement. A simple mathematical model showed that even in extreme situations, ignoring population movement since the last census is unlikely to have any appreciable effect. Rates of homogeneity did not differ systematically between the surveys. CONCLUSIONS: In situations where quality of fieldwork can be guaranteed, the EPI random walk method can give accurate and precise results. However, compact segment sampling is generally to be preferred as it ensures objectivity in household selection and permits the estimation of population totals (such as those unvaccinated), which are helpful for planning service provision.