The Marine Isotope Stage 16–15 boundary (Termination VII) is the first deglacial warming step of the late Quaternary following the mid-Pleistocene transition (MPT), when 41 kyr climatic cycles shifted to strong 100 kyr cycles. The detailed structure of this important climatic event has remained unknown until now. Core MV0508-19JPC from Santa Barbara Basin, California, contains a decadal-scale climatic and geochemical sediment record of 4000 years duration that includes the early part of this deglacial episode. This record reveals that the climatic shift during the early deglacial occurred rapidly (<700 years), in a progression of three abrupt warming steps. The onset of Marine Isotope Stage (MIS) 15 was remarkably abrupt with 4–5°C sea surface warming in ~50 years. The deglacial sequence contains the well-dated Lava Creek tephra (631.3 ± 4 ka) from Yellowstone Caldera used to date the onset of Termination VII at 631.5 ka. The late MIS 16 and early MIS 15 interval exhibits multiple decadal-scale negative excursions in δ¹³C of planktic foraminifera, likely the result of repeated discharges of methane from methane hydrates associated with both ocean warming and low sea level. A warm interstadial that interrupts late MIS 16 is marked by elevated concentrations of redox-sensitive elements indicating sulfidic, oxygen-deficient bottom and pore-waters, and elevated concentrations of total organic carbon and Cd, reflecting increased surface productivity. Unlike younger sediments on the California margin, these indicators of increased productivity and low dissolved oxygen do not consistently correspond with each other or with preserved laminations, possibly reflecting instability of a still evolving ocean-atmosphere system following the MPT.