Sub-sea-floor sediments may contain two-thirds of Earth's total prokaryotic biomass. However, this has its basis in data extrapolation from ~500-meter to 4-kilometer depths, whereas the deepest documented prokaryotes are from only 842 meters. Here, we provide evidence for low concentrations of living prokaryotic cells in the deepest (1626 meters below the sea floor), oldest (111 million years old), and potentially hottest (~100 degrees C) marine sediments investigated. These Newfoundland margin sediments also have DNA sequences related to thermophilic and/or hyperthermophilic Archaea. These form two unique clusters within Pyrococcus and Thermococcus genera, suggesting unknown, uncultured groups are present in deep, hot, marine sediments (~54 degrees to 100 degrees C). Sequences of anaerobic methane-oxidizing Archaea were also present, suggesting a deep biosphere partly supported by methane. These findings demonstrate that the sub-sea-floor biosphere extends to at least 1600 meters below the sea floor and probably deeper, given an upper temperature limit for prokaryotic life of at least 113 degrees C and increasing thermogenic energy supply with depth.