Kittur et al. (2004, 2006) and Jung & Hummel (2009, 2011) showed that people have great difficulty learning relation-based categories with a probabilistic (i.e., family resemblance) structure, in which no single relation is shared by all members of a category. Yet acquisition of such categories is not strictly impossible: In all these studies, roughly half the subjects eventually reached criterion. What are these subjects doing that the other half are not? We hypothesized that successful subjects were those who divided the nominal categories into two or more sub-categories, each of which individually has a deterministic structure. We report an experiment testing and supporting this hypothesis: Explicitly presenting subjects with hierarchical (category and sub-category) structures facilitated the acquisition of otherwise probabilistic relational categories.