State-building is normally associated with the creation of institutions such as the army, police force, judiciary, and political system. Using the Palestinian case of state-building, the paper relies on constructivist analysis to examine the use of surveillance as a discursive practice in state construction. Two central aspects of surveillance practices are considered in this paper: population count and spatial monitoring. Examination of these practices is situated in the asymmetrical power relations between Israel and the Palestinians. Conflict over land and people is manifested in the construction of citizenship, identity, and geographical boundaries. The paper examines the historical and contemporary role of the population census in both the Palestinian and Israeli case in the social construction of spaces and the categorization of people. Zureik draws his examples from the first Israeli census, taken in 1948, the monitoring of Palestinian refugees by the United Nations, and the contest over Jerusalem and borders as a consequence of the Oslo Agreement.