The All-Union Congress of Soviets ratified the Constitution of the USSR on 31 January 1924 and, according to traditional narratives, brought the formation of the Soviet Union to a close. The very same day, a group of leading ethnographers met at the Academy of Sciences in Petrograd to discuss a directive they had received from the Soviet of Nationalities: define nationality, determine “rational criteria” for classifying the population in the first All-Union Census, and notify the Central Statistical Administration as soon as possible. The legal formation of the Soviet Union had been completed, but the state-building process, which involved “re-imagining” the former Russian empire as a socialist federation of nationalities, was just getting under way. This essay argues that the classification of Soviet citizens by nationality in the All-Union Censuses of 1926, 1937, and 1939 was a fundamental component of the creation of the multinational state. The very establishment of the census category nationality marked a critical break with the tsarist regime, which had categorized its subjects on the basis of religion and native language. Ethnographers, statisticians, and linguists from Minsk to Vladivostok who formulated questionnaires and drew up lists of nationalities for all three censuses used their expertise to divine order out of chaos and create a new definitional grid. Not only did they have to decide which tribes, clans, and peoples belonged to which nationality, they also had to figure out what “nationality” meant.