The psychological mechanisms that subserve inductions about novel social categories in childhood are hotly debated. While research demonstrated that language, and in particular generic statements, plays a major role in how children learn to attribute properties to social categories, developmental theories propose other mechanisms. One theoretical account holds that the mere act of labeling social categories is sufficient for children to generalize properties to category members, because labels are considered as referring to significant, homogeneous kinds of people. A second theoretical account proposes that children generalize properties to category members from statistical evidence, that is, by directly observing regularities in their environment. The present study assessed those two hypotheses, by testing (via an online experiment) the effects of simple category labels and observation of statistical evidence on European 4- to 6-year-olds (N = 88) and 7- to 9-year-olds' (N = 92) predictions about novel social categories. From around 7 to 9 years, children generalized properties to category members based on simple category labels or on their observation of a majority of unlabeled category members having the same property. Four- to 6-year-old children, however, made similarity inferences only when both labels and statistical evidence were combined. Overall, the present study highlights a developmental shift from an early limited tendency to make similarity inferences to a later propensity to infer similarity from small evidence. These findings deepen our understanding of the conditions under which children start to make similarity inferences. Implications for the acquisition of stereotypes are also discussed.