The flow of a uniform Bose gas at speeds greater than the Landau critical velocity
vc does not necessarily destroy superfluidity, but rather needs only to lead to a decrease of the superfluid mass density ${\ensuremath{\rho}}_{s}$. Analyzing a weakly interacting Bose gas with a finite-range interparticle interaction that leads to a Landau critical velocity at nonzero quasiparticle momentum, we explicitly construct the (nonuniform) condensate for fluid flow faster than
vc and calculate the accompanying decrease in ${\ensuremath{\rho}}_{s}$. We briefly comment on the relation of the physics to other problems in superfluids, e.g., solitons and vortices in Bose-Einstein condensates, and critical currents in superconductors.