Recent research suggests that some human-like social skills evolved in dogs (Canis familiaris) during domestication as an incidental by-product of selection for “tame” forms of behavior. It is still possible, however, that the social skills of certain dog breeds came under direct selection that led to further increases in social problem solving ability. To test this hypothesis, different breeds of domestic dogs were compared for their ability to use various human communicative behaviors to find hidden food. We found that even primitive breeds with little human contact were able to use communicative cues. Further, “working” dogs (shepherds and huskies: thought to be bred intentionally to respond to human cooperative communicative signals) were more skilled at using gestural cues than were non-working breeds (basenji and toy poodles: not thought to have been bred for their cooperative-communicative ability). This difference in performance existed regardless of whether the working breeds were more or less genetically wolf-like. These results suggest that subsequent to initial domesticating selection giving rise to cue-following skills, additional selection on communicative abilities in certain breeds has produced substantive differences in those breeds' abilities to follow cues.