Learning in the prototype distortion task is thought to involve perceptual learning in which category members experience an enhanced visual response (Ashby & Maddox, 2005). This response likely leads to more efficient processing, which in turn may result in a feeling of perceptual fluency for category members. We examined the perceptual fluency hypothesis by manipulating fluency independently from category typicality. We predicted that when perceptual fluency was induced using subliminal priming, this fluency would be misattributed to category membership and would affect categorization decisions. In a prototype distortion task, participants were more likely to judge non-members as category members when they were made perceptually fluent with a matching subliminal prime. This result suggests that perceptual fluency can be reflective of category membership and may be used as a cue during some categorization decisions. In addition, the results provide converging evidence that some types of categorization are based on perceptual learning.