There has been a growing interest in the cognitive skills of domestic dogs, but most current knowledge about dogs’ understanding of their environment is limited to the visual or auditory modality. Although it is well known that dogs have an excellent olfactory sense and that they rely on olfaction heavily when exploring the environment or recognizing individuals, it remains unclear whether dogs perceive odors as representing specific objects. In the current study, we examined this aspect of dogs’ perception of the world. Dogs were presented with a violation-of-expectation paradigm in which they could track the odor trail of one target (Target A), but at the end of the trail, they found another target (Target B). We explored (a) what dogs expect when they smell the trail of an object, (b) how they search for an object, and (c) how their educational background influences their ability to find a hidden object, by comparing family dogs and working dogs that had passed exams for police or rescue dogs. We found that all subjects showed a flexible searching behavior, with the working dogs being more effective but the family dogs learning to be effective over trials. In the first trial, dogs showed measurable signs of “surprise” (i.e., further searching for Target A) when they found Target B, which did not correspond to the odor of Target A from the trail. We conclude that dogs represent what they smell and search flexibly, which is independent from their educational background.