Prior categorization studies have shown that pigeons reliably track features that are relevant to category discrimination. In these studies, category exemplars contained two relevant and two irrelevant features; therefore, category density (specifically, the relevant to irrelevant information ratio) was relatively high. Here, we manipulated category density both between and within subjects by keeping constant the amount of relevant information (one feature) and varying the amount of irrelevant information (one or three features). One group of pigeons started with low-density training, then proceeded to high-density training, and finally returned to low-density training (Low-High-Low); a second group of pigeons started with high-density training and then proceeded to low-density training (High-Low). The statistical density of the category exemplars had a large effect on pigeons’ performance. Training with high-density exemplars greatly benefitted category learning. Accuracy rose faster and to a higher level with high-density training than with low-density training; the percentage of relevant pecks showed a very similar pattern. In addition, high-density training (in the Low-High-Low group) led to an increase in performance on the more difficult low-density task, an observation reminiscent of the easy-to-hard effect. These results illuminate factors affecting pigeons’ accuracy and tracking of relevant information in visual categorization.