Growing evidence shows that dogs can complete complex behavioral tasks, such as learning labels for hundreds of objects, readily learning the name of a novel object, and responding differentially to objects by category (e.g., “toy,” “ball,” “Frisbee”). We expand here on the evidence for complex behavioral abilities in dogs by demonstrating that they are capable of concept formation by strict criteria. A German shepherd responded differentially to two sets of objects (“toys” and “non-toys”) in Experiment 1. Additionally, the dog’s differential responding in Experiment 1 occurred from the first trial, indicating that he entered the experiment with this stimulus class already differentiated from his day-to-day exposure to contingencies. In Experiment 2 we used a common response (tug-of-war) with three objects that were not retrieved in Experiment 1 to attempt to add these objects to the stimulus class. After repeated sessions of tug-of-war, the dog began retrieving all three objects in the retrieval test, although the rates of retrieval varied between objects. Finally, in Experiment 3, we conducted a transfer of function test in which the dog emitted a new response to untrained exemplars suggesting that his differential responding in Experiment 1 was indicative of a concept by the strictest criteria. Additionally, the reliably emitted the new response in the transfer test to one of the three new objects from Experiment 2, suggesting this object had been reliably added to the conceptual class.