Nuclear war would produce dire global consequences for humans and our environment. We simulated climate impacts of US-Russia and India-Pakistan nuclear wars in an Earth System Model, here, we report on the ocean impacts. Like volcanic eruptions and large forest fires, firestorms from nuclear war would transport light-blocking aerosols to the stratosphere, resulting in global cooling. The ocean responds over two timescales: a rapid cooling event and a long recovery, indicating a hysteresis response of the ocean to global cooling. Surface cooling drives sea ice expansion, enhanced meridional overturning, and intensified ocean vertical mixing that is expanded, deeper, and longer lasting. Phytoplankton production and community structure are highly modified by perturbations to light, temperature, and nutrients, resulting in initial decimation of production, especially at high latitudes. A new physical and biogeochemical ocean state results, characterized by shallower pycnoclines, thermoclines, and nutriclines, ventilated deep water masses, and thicker Arctic sea ice. Persistent changes in nutrient limitation drive a shift in phytoplankton community structure, resulting in increased diatom populations, which in turn increase iron scavenging and iron limitation, especially at high latitudes. In the largest US-Russia scenario (150 Tg), ocean recovery is likely on the order of decades at the surface and hundreds of years at depth, while changes to Arctic sea-ice will likely last thousands of years, effectively a “Nuclear Little Ice Age”. Marine ecosystems would be highly disrupted by both the initial perturbation and in the new ocean state, resulting in long-term, global impacts to ecosystem services such as fisheries.