We revisit the question of stability of holographic superfluids with finite superfluid velocity. Our method is based on applying the Landau criterion to the Quasinormal Mode (QNM) spectrum. In particular we study the QNMs related to the Goldstone modes of spontaneous symmetry breaking with linear and quadratic dispersions.In the linear case we show that the sound velocity becomes negative for large enough superfluid velocity and that the imaginary part of the quasinormal frequency moves to the upper half plane. Since the instability is strongest at finite wavelength, we take this as an indication for the existence of an inhomogeneous or striped condensed phase for large superfluid velocity. In the quadratic case the instability is present for arbitrarily small superfluid velocity.