We study experimentally the effect of linear plasma density gradients on the self-modulation of a 400 GeV proton bunch. Results show that a positive or negative gradient increases or decreases the number of microbunches and the relative charge per microbunch observed after 10 m of plasma. The measured modulation frequency also increases or decreases. With the largest positive gradient we observe two frequencies in the modulation power spectrum. Results are consistent with changes in wakefields' phase velocity due to plasma density gradients adding to the slow wakefields' phase velocity during self-modulation growth predicted by linear theory.