In a recent study, Wasserman, Kain, and O'Donoghue (Current Biology, 33(6), 1112–1116, 2023) set out to resolve the associative learning paradox by showing that pigeons can solve a complex category learning task through associative learning. The present Outlook paper presents their findings, expands on this paradox, and discusses implications of their results.