The Middle and Late Pleistocene is arguably the most interesting period in human evolution. This broad period witnessed the evolution of our own lineage, as well as that of our sister taxon, the Neanderthals, and related Denisovans. It is exceptionally rich in both fossil and archaeological remains, and uniquely benefits from insights gained through molecular approaches, such as paleogenetics and paleoproteomics, that are currently not widely applicable in earlier contexts. This wealth of information paints a highly complex picture, often described as ‘the Muddle in the Middle,’ defying the common adage that ‘more evidence is needed’ to resolve it. Here we review competing phylogenetic scenarios and the historical and theoretical developments that shaped our approaches to the fossil record, as well as some of the many remaining open questions associated with this period. We propose that advancing our understanding of this critical time requires more than the addition of data and will necessitate a major shift in our conceptual and theoretical framework.