The first post-Soviet censuses were taken between February 1999 in Belarus and October 2002 in the Russian Federation. They raise interesting issues on the complex links existing between politics and administration, statistical continuity and international recommendations, the adjustment to new situations and the territorial stakes involved. The census questions, particularly those regarding language, ethnicity and migration status, reflect the confrontation of these competing claims and the necessary political compromises that were reached. Here, Dominique Arel examines the census procedures and analyses in detail how the phrasing of the questions was elaborated by the statistical offices in Russia, Ukraine, Belarus, Kazhakstan and the Baltic states. This approach throws light on the political construction of the categories that were finally adopted.