Mesopelagic fish are integral to ocean food webs and play an important role in carbon transport through their vertical migration behavior. Ocean deoxygenation caused by anthropogenic warming is expected to pose severe threats to mesopelagic fauna by enhancing physical stress and changing predator-prey relationships. In agreement with this expectation, our fish otolith record in a Mediterranean sediment core shows near absence of mesopelagic species during Sapropel deposition between ~7 and ~10 thousand years ago, concurrent with high surface productivity and low oxygenation of mid-depth waters. Instead, the otolith record is dominated by fish species adapted to epipelagic habitats, including European anchovy (Engraulis encrasicolus) and silvery lightfish (Maurolicus muelleri). Subsequent reoxygenation starting ~7 thousand years ago is accompanied by a three-fold increase in total otolith abundance. The large majority of these are mesopelagic lanternfish (Myctophidae) that dominate the otolith assemblage from the middle-Holocene to the present. Our findings corroborate expectations that future expansion of midwater deoxygenation could severely deplete mesopelagic fish communities over the coming centuries, with major impacts on marine fisheries, marine conservation, ocean food web structure, carbon storage and other marine ecosystem services.