Space-time structured laser pulses feature an intensity peak that can travel at an arbitrary velocity while maintaining a near-constant profile. These pulses can propagate in uniform media, where their frequencies are correlated with continuous transverse wavevectors, or in structured media, such as a waveguide, where their frequencies are correlated with discrete mode numbers. Here, we demonstrate the formation and propagation of arbitrary-velocity laser pulses in a plasma waveguide where the intensity can be orders of magnitude higher than in a solid-state waveguide. The flexibility to control the velocity of the peak intensity in a plasma waveguide enables new configurations for plasma-based sources of radiation and energetic particles, including THz generation, laser wakefield acceleration, and direct laser acceleration.