While the use of fire has long been recognised as a crucial innovation in the cultural evolution of humankind, much research has focused on the (debated) chronology of its earliest use and control, and less on the ways in which fire was used in the deep past. At its latest by the Upper Palaeolithic, hunter-gatherers routinely used fire to heat a wide range of materials, adjusting parameters like temperature, exposure time and fuel type to the specific requirements of the treated materials, for instance in food preparation or tool production. Comparing analyses of the chemical and physical properties of modern materials, heated under a range of controlled conditions in a laboratory, to archaeological ones might allow the reconstruction of the "heating history" of excavated materials and hence to infer the function of particular fires in the past - provided changes affecting the properties of the heated archaeological material during burial time are taken into consideration. To investigate the feasibility of such an approach, heated materials sampled from 40,000 to 25,000 year old fireplaces (hearths) and their sedimentary matrices from the Upper Palaeolithic Abri Pataud rock shelter in South-Western France are used here to study (1) the fuel type(s) used by the site's occupants, (2) the temperatures reached in fireplaces and (3) the potential changes in human activities related to fireplaces over time, with the influence of post-depositional processes taken into explicit consideration throughout. For this purpose, we used a range of methods to analyse macroscopically visible as well as "invisible" (microscopic and molecular) heat-altered materials. The results suggest that charred organic materials (COM) encountered in the samples predominantly result from the fuel used in fireplaces, including the earliest reported use of dung as fuel. Earlier suggestions about the use of bone as fuel at the Abri Pataud are not supported by this study. The heating temperature of COM increased gradually from 350 degrees C in the Aurignacian to 450 degrees C in Gravettian levels. Py-GC MS studies identified a range of organic compounds, biomolecules derived from plant as well as animal sources, still preserved in the sediments after exposure to heat and burial in the rock shelter more than 20,000 years ago. Mammalian mtDNA was identified in sediment samples retrieved from the fireplaces, including ancient mtDNA fragments that originated from one or more modern human-like mitochondrial genome(s). This makes the Abri Pataud the first archaeological site for which ancient modern human mtDNA has been retrieved from sediment samples. The absence of specific organic compounds (furans) in the Aurignacian levels and their presence in the Gravettian ones, the changes in temperatures reached through the Aurignacian-Gravettian sequence as well as changes in the character of the fireplaces (presence/absence of lining river pebbles) suggest that the functions of hearths changed through time. These results highlight the potential of multi-proxy analyses of macro- and microscopic traces of ancient fireplaces, and especially of a shift in focus towards molecular traces of such activities. Systematic sampling of fireplaces and their sedimentary matrix should become a standard part of the excavation protocol of such features, to improve our understanding of the activities of humans in the deep past.