Concepts contain rich structures that support flexible semantic cognition. These structures can be characterized by patterns of feature covariation: Certain features tend to cluster in the same items (e.g., "feathers," "wings," "can fly"). Existing computational models demonstrate how this kind of structure can be leveraged to slowly learn the distinctions between categories, on developmental timescales. However, it is not clear whether and how we leverage feature structure to quickly learn a novel category. We thus investigated how the internal structure of a new category is first extracted from experience, with the prediction that feature-based structure would have a rapid and broad influence on the learned category representation. Across three experiments, novel categories were designed with patterns of feature associations determined by carefully constructed graph structures, with Modular graphs--exhibiting strong clusters of feature covariation--compared against Random and Lattice graphs. In Experiment 1, a feature inference task using verbal stimuli revealed that Modular structure broadly facilitated category learning. Experiment 2 replicated this effect in visual categories. In Experiment 3, a statistical learning paradigm revealed that this Modular benefit relates to high-level structure rather than pairwise feature associations and persists even when category structure is incidental to the task. A neural network model was readily able to account for these effects, suggesting that correlational feature structure may be encoded within rapidly learned, distributed category representations. These findings constrain theories of category representation and link theories of category learning with structure learning more broadly.