Satellite telemetry studies of the movements of seabirds are now common and have revealed impressive flight capabilities and extensive distributions among individuals and species at sea. Linking seabird movements with environmental conditions over vast expanses of the world's open ocean, however, remains difficult. Seabirds of the order Procellariiformes (e.g., petrels, albatrosses, and shearwaters) depend largely on wind and wave energy for efficient flight. We present a new method for quantifying the movements of far-ranging seabirds in relation to ocean winds measured by the SeaWinds scatterometer onboard the QuikSCAT satellite. We apply vector correlation (as defined by Crosby et al. in J Atm Ocean Tech 10:355-367, 1993) to evaluate how the trajectories (ground speed and direction) for five procellariiform seabirds outfitted with satellite transmitters are related to ocean winds. Individual seabirds (Sooty Shearwater, Pink-footed Shearwater, Hawaiian Petrel, Grey-faced Petrel, and Black-footed Albatross) all traveled predominantly with oblique, isotropic crossing to quartering tail-winds (i.e., 105-165 degrees in relation to birds' trajectory). For all five seabirds, entire track line trajectories were significantly correlated with co-located winds. Greatest correlations along 8-day path segments were related to wind patterns during birds' directed, long-range migration (Sooty Shearwater) as well as movements associated with mega-scale meteorological phenomena, including Pacific Basin anticyclones (Hawaiian Petrel, Grey-faced Petrel) and eastward-propagating north Pacific cyclones (Black-footed Albatross). Wind strength and direction are important factors related to the overall movements that delineate the distribution of petrels at sea. We suggest that vector correlation can be used to quantify movements for any marine vertebrate when tracking and environmental data (winds or currents) are of sufficient quality and sample size. Vector correlation coefficients can then be used to assess population--or species-specific variability and used to test specific hypotheses related to how animal movements are associated with fluid environments.