Neuropsychological and developmental studies suggest human musical ability has a deep evolutionary history; but we do not find evidence of the manufacture and use of instruments, with which musical behaviours have often been assumed to be equated, until 70,000 years after the advent of Homo sapiens. This anomaly is addressed by examining the evidence from the fossil record for the evolution of the physiology and neurology required for musical behaviours, with the aim of identifying the development of the physiological and neurological capacity to produce and process melody and/or rhythm. Aural and vocal sophistication appear to have developed in tandem, beginning with full bipedalism around 1.75 million years ago, until a vocal apparatus similar to the modern was present in Homo heidelbergensis 400,000–300,000 years ago. Prosodic and structural aspects of both speech and music production and processing are lateralized in the brain in similar ways suggesting evolutionarily-shared foundations for these mechanisms.