The effects of two different kinds of categorization training were investigated. In observational training, observers are presented with a category label and then shown an exemplar from that category. In feedback training, they are shown an exemplar, asked to assign it to a category, and then given feedback about the accuracy of their response. These two types of training were compared as observers learned two types of category structures--those in which optimal accuracy could be achieved via some explicit rule-based strategy, and those in which optimal accuracy required integrating information from separate perceptual dimensions at some predecisional stage. There was an overall advantage for feedback training over observational training, but most importantly, type of training interacted strongly with type of category structure. With rule-based structures, the effects of training type were small, but with information-integration structures, accuracy was substantially higher with feedback training, and people were less likely to use suboptimal rule-based strategies. The implications of these results for current theories of category learning are discussed.