Cognitive archaeologists infer from material remains to the cognitive features of past societies. We characterize cognitive archaeology in terms of trace-based reasoning, which in the case of cognitive archaeology involves inferences drawing upon background theory linking objects from the archaeological record to cognitive features. We analyse such practices, examining work on cognitive evolution, language, and musicality. We argue that the central epistemic challenge for cognitive archaeology is often not a paucity of material remains, but insufficient constraint from cognitive theories. However, (...) we also argue that the success of cognitive archaeology does not necessarily require well-developed cognitive theories: Success might instead lead to them. (shrink)