DENITRIFICATION-the process by which nitrate is reduced to gaseous nitrogen species (usually N-2 or N2O)-is the dominant mechanism for removal of fixed nitrogen from the biosphere. In the oceans, denitrification is mediated by bacteria in suboxic environments and, by controlling the supply of fixed nitrogen, is an important limiting factor for marine productivity(1-3). Denitrification produces substantial N-15 enrichment in subsurface nitrate(4-6), which is reflected in the isotopic composition of sinking particulate nitrogen(7); sediment N-15/N-14 ratios in regions with suboxic water columns may therefore provide a record of past changes in denitrification intensity. Here we report nitrogen isotope data for sediment cores from three sites in the Arabian Sea. At all three sites we find large, near-synchronous downcore variations in N-15/N-14, which are best explained by regional changes in the isotopic composition of subsurface nitrate, and hence denitrification. Moreover, these variations are synchronous with Milankovitch cycles, thereby establishing a link with climate. We argue that these large, climate-linked variations, in a region that contributes significantly to global marine denitrification, are likely to have perturbed marine biogeochemical cycles during the Late Quaternary period.