Traveling waves in actin have recently been reported in many cell types. Fish keratocyte cells, which usually exhibit rapid and steady motility, exhibit traveling waves of protrusion when plated on highly adhesive surfaces. We hypothesize that waving arises from a competition between actin polymerization and mature adhesions for VASP, a protein that associates with growing actin barbed ends. We developed a mathematical model of actin protrusion coupled with membrane tension, adhesions and VASP. The model is formulated as a system of partial differential equations with a nonlocal integral term and noise. Simulations of this model lead to a number of predictions, for example, that overexpression of VASP prevents waving, but depletion of VASP does not increase the fraction of cells that wave. The model also predicts that VASP exhibits a traveling wave whose peak is out of phase with the F-actin wave. Further experiments confirmed these predictions and provided quantitative data to estimate the model parameters. We thus conclude that the waves are the result of competition between actin and adhesions for VASP, rather than a regulatory biochemical oscillator or mechanical tag-of-war. We hypothesize that this waving behavior contributes to adaptation of cell motility mechanisms in perturbed environments.