Background: The present time reflects a period of intense effort to get the most out of public health interventions, with an emphasis on health systems reform and implementation research. Population health approaches to determine which combinations are better at achieving the goals of improved health and well-being are needed to provide a ready response to the need for timely and real-world piloting of promising interventions. Objective: This paper describes the steps needed to establish a population health surveillance site in order to share the lessons learned from our experience launching the Nahuche Health and Demographic Surveillance System (HDSS) in a relatively isolated, rural district in Zamfara, northern Nigeria, where strict Muslim observance of gender separation and seclusion of women must be respected by any survey operation. Discussion: Key to the successful launch of the Nahuche HDSS was the leadership's determination, stakeholder participation, support from state and local government areas authorities, technical support from the INDEPTH Network, and international academic partners. Solid funding from our partner health systems development programme during the launch period was also essential, and provided a base from which to secure long-term sustainable funding. Perhaps the most difficult challenges were the adaptations needed in order to conduct the requisite routine population surveillance in the communities, where strict Muslim observance of gender separation and seclusion of women, especially young women, required recruitment of female interviewers, which was in turn difficult due to low female literacy levels. Local community leaders were key in overcoming the population's apprehension of the fieldwork and modern medicine, in general. Continuous engagement and sensitisation of all stakeholders was a critical step in ensuring sustainability. While the experiences of setting up a new HDSS site may vary globally, the experiences in northern Nigeria offer some strategies that may be replicated in other settings with similar challenges.