The present research explored the effects of stimulus and task factors on preschoolers' (Experiments 1 and 3) and adults' (Experiment 2) tendency to categorize according to taxonomic relations, when those relations conflict with appearances. In Experiment 1, we examined the effects of and interactions among (a) available information, operationalized by using more- or less-informative stimulus types (objects vs. line drawings) and by the presence or absence of labeling, and (b) task constraints, operationalized by comparing sorting questions with inductive inferences questions. When provided with information that constrained the categorization decision, either through the availability of labels or a combination of enhanced physical informativeness of objects and an inference question, preschoolers reliably based their categorization decisions on taxonomic relations between physically dissimilar items. In Experiment 2, stimulus type (objects vs. line drawings) was shown to have a similar effect on adults. In Experiment 3, we examined the effects of stimulus type on preschoolers' inductive inferences and accuracy of naming. The effects in the two tasks were closely related, suggesting that the amount of available information affects different responses in similar ways. These data demonstrate the interactive effects of available information and task constraints on categorization decisions.