Constraining variations in marine N2-fixation over glacial-interglacial timescales is crucial for determining the role of the marine nitrogen cycle in modifying ocean productivity and climate, yet paleo-records from N2-fixation regions are sparse. Here we present new nitrogen isotope (δ15N) records of bulk sediment and foraminifera test-bound (FB) nitrogen extending back to the last ice age from the oligotrophic Gulf of Mexico (GOM). Previous studies indicate a substantial terrestrial input during the last ice age and early deglacial, for which we attempt to correct the bulk sediment δ15N using its observed relationship with the C/N ratio. Both corrected bulk and FB- δ15N reveal a substantial glacial-to-Holocene decrease of δ15N toward Holocene values of around 2.5 %, similar to observations from the Caribbean. This δ15N change is most likely due to a glacial-to-Holocene increase in regional N2-fixation. A deglacial peak in the FB-δ15N of thermocline dwelling foraminifera Orbulina universa probably reflects a whole ocean increase in the δ15N of nitrate during deglaciation. The δ15N of the surface dwelling foraminifera Globigerinoides ruber and the corrected bulk δ15N show little sign of this deglacial peak, both decreasing from last glacial values much earlier than does the δ15N of O. universa; this may indicate that G. ruber and bulk N reflect the euphotic zone signal of an early local increase in N 2-fixation. Our results add to the evidence that, during the last ice age, the larger iron input from dust did not lead to enhanced N 2-fixation in this region. Rather, the glacial-to-Holocene decrease in δ15N is best explained by a response of N 2-fixation within the Atlantic to the deglacial increase in global ocean denitrification. © 2011 by the American Geophysical Union.