Contourites in the Gulf of Cádiz (GC) preserve a unique archive of Mediterranean Outflow Water (MOW) variability over the past 5.3 Ma. In our study, we investigate the potential of geochemical data obtained by XRF scanning to decipher bottom current processes and paleoclimatic evolution at two different sites drilled during IODP Expedition 339 through contourites in the northern GC: Site U1387, which is bathed by the upper MOW core, and Site U1389, located more proximal to the Strait of Gibraltar. The lack of major downslope transport during the Pleistocene makes both locations ideally suited for our study. The results indicate that the Zr/Al ratio, representing the relative enrichment of heavy minerals (zircon) over less dense alumnosilicates under fast bottom current flow, is the most useful indicator for a semiquantitative assessment of current velocity. Although most elements are biased by current-related processes, the bromine (Br) record, representing organic content, preserves the most pristine climate signal rather independent of grain-size changes. Hence, Br can be used for chronostratigraphy and site-to-site correlation in addition to stable isotope stratigraphy. Based on these findings, we reconstructed MOW variability for Marine Isotope Stages (MIS) 1–5 using the Zr/Al ratio from Site U1387. The results reveal abrupt, millennial-scale variations of MOW strength during Greenland Stadials (GS) and Interstadials (GI) with strong MOW during GS and glacial Terminations and a complex behavior during Heinrich Stadials. Millennial-scale variability persisting during periods of poorly expressed GS/GI cyclicities implies a strong internal oscillation of the Mediterranean/North Atlantic climate system.